Detta dokument tar upp problemet med påvisbart effektiva och praktiskt taget bra on-the-fly determinacy ras upptäckt i uppgift parallella program som använder futures. Tidigare arbeten på determinacy ras detektion har mestadels fokuserat på antingen uppgift parallella program som följer en serie-parallell beroende struktur eller de med obegränsad användning av futures som genererar godtyckliga beroenden. I detta arbete överväger vi en begränsad användning av futures och visar att vi kan upptäcka raser mer effektivt än med allmän användning av futures. Vi presenterar två algoritmer: MultiBags och MultiBags+. MultiBags riktar program som använder futures på ett begränsat sätt och körs i tid O(T 1 α(m, n)), där T 1 är den sekventiella körtiden för programmet, α är den inversa Ackermann funktion, m är det totala antalet minnesåtkomster, n är det dynamiska antalet platser där parallellism skapas. Eftersom α är en mycket långsamt växande funktion (som begränsas av 4 för alla praktiska ändamål), kan det behandlas som en nära till konstant overhead. MultiBags+ är en förlängning av MultiBags som riktar program med allmän användning av terminer. Den körs i tiden O((T 1 + k 2 )α(m, n)) där T 1, α, m och n definieras som tidigare, och k är antalet framtida operationer i beräkningen. Vi implementerade både algoritmer och empiriskt demonstrerar deras effektivitet.
För allmän användning av terminer, Utterback m.fl. Ref föreslog en algoritm (och dess motsvarande genomförande) som utför i tid O((T 1 + k 2 )α(m, n)).
Efficient race detection with futures
{'venue': None, 'journal': 'Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming', 'mag_field_of_study': ['Computer Science']}