Spekulacyjna wielowątkowość

Spekulacja na poziomie wątków (TLS), znana również jako wielowątkowość spekulacyjna lub równoległość spekulacyjna, to technika spekulatywnego wykonywania sekcji kodu komputerowego, która ma zostać wykonana później równolegle z normalnym wykonaniem w oddzielnym niezależnym wątku . Taki wątek spekulacyjny może wymagać przyjęcia założeń dotyczących wartości zmiennych wejściowych. Jeśli okażą się one nieważne, wówczas części spekulatywnego wątku, które opierają się na tych zmiennych wejściowych, będą musiały zostać odrzucone i zgniecione. Jeśli założenia są poprawne, program może zakończyć się w krótszym czasie, pod warunkiem, że wątek będzie mógł być efektywnie zaplanowany.

Opis

TLS wyodrębnia wątki z kodu szeregowego i wykonuje je spekulacyjnie równolegle z bezpiecznym wątkiem. Wątek spekulatywny będzie musiał zostać odrzucony lub uruchomiony ponownie, jeśli jego założenia dotyczące stanu wejściowego okażą się nieważne. Jest to dynamiczna (w czasie wykonywania) równoległości , która może odkryć równoległość, której techniki równoległości statycznej (w czasie kompilacji) mogą nie wykorzystać, ponieważ w czasie kompilacji nie można zagwarantować niezależności wątków. Aby technika osiągnęła cel, jakim jest skrócenie ogólnego czasu wykonywania, musi być dostępny zasób procesora, który może być skutecznie wykonywany równolegle z głównym bezpiecznym wątkiem.

TLS zakłada optymistycznie, że dana część kodu (zwykle pętle) może być bezpiecznie wykonywana równolegle. W tym celu dzieli przestrzeń iteracji na fragmenty, które są wykonywane równolegle przez różne wątki. Monitor sprzętowy lub programowy zapewnia zachowanie semantyki sekwencyjnej (innymi słowy, wykonanie przebiega tak, jakby pętla była wykonywana sekwencyjnie). Jeśli pojawi się naruszenie zależności, ramy spekulatywne mogą zatrzymać całe równoległe wykonanie i wznowić je; zatrzymywania i ponownego uruchamiania wątków naruszających prawo oraz wszystkich ich następców, w celu zasilenia ich poprawnymi danymi; lub zatrzymać wyłącznie wątek naruszający prawo i jego następców, którzy pobrali z niego nieprawidłowe dane.

Dalsza lektura

• Yiapanis, Paraskevas; Brązowy, Gavin; Lujan, Mikel (2016). „Spekulacja oprogramowania sterowana przez kompilator dla równoległości na poziomie wątków” . Transakcje ACM dotyczące języków i systemów programowania . 38 (2): 1–45. doi : 10.1145/2821505 .

• Yiapanis, Paraskevas; Rosas-Ham, Demian; Brązowy, Gavin; Lujan, Mikel (2013). „Optymalizacja systemów wykonawczych oprogramowania pod kątem spekulatywnej równoległości” . Transakcje ACM dotyczące architektury i optymalizacji kodu . 9 (4): 1–27. doi : 10.1145/2400682.2400698 .
•   Llanos, Diego R. (2007). „Nowe strategie planowania dla losowych algorytmów przyrostowych w kontekście spekulatywnej równoległości” . Transakcje IEEE na komputerach . 56 (6): 839–852. doi : 10.1109/TC.2007.1030 . S2CID 3181243 .
• Johnson, Nick P.; Kim, Hanjun; Prabhu, Prakasz; Zaks, Ayal; Sierpień, David I. (2012). „Separacja spekulacyjna w celu prywatyzacji i redukcji” (PDF) . Materiały z 33. Konferencji ACM SIGPLAN na temat projektowania i wdrażania języka programowania . PLD '12. s. 359–370. doi : 10.1145/2254064.2254107 .
• Bhowmik, Anasua; Franklin, Manoj (2002). „Ogólna struktura kompilatora dla wielowątkowości spekulacyjnej”. Materiały z czternastego dorocznego sympozjum ACM na temat algorytmów i architektur równoległych . SPAA '02. s. 99–108. doi : 10.1145/564870.564885 .
• Bruening, Derek; Devabhaktuni, Srikrishna; Amarasinghe, Saman (2000). Softspec: równoległość spekulacyjna oparta na oprogramowaniu (PDF) . FDDO-3. s. 1–10.
• Chen, Michael K.; Olukotun, Kunle (1998). „Wykorzystywanie równoległości na poziomie metody w jednowątkowych programach Java”. Międzynarodowa konferencja na temat architektur równoległych i technik kompilacji . PAKT 1998. s. 176–184. doi : 10.1109/PACT.1998.727190 .
• Chen, Michael K.; Olukotun, Kunle (2003). „System Jrpm do dynamicznego paralelizowania programów Java” . Materiały z 30. dorocznego międzynarodowego sympozjum poświęconego architekturze komputerów . ISCA '03. s. 434–446. doi : 10.1145/859618.859668 .
• Cintra, Marcelo; Llanos, Diego R. (2003). „W kierunku wydajnej i niezawodnej równoległości spekulacyjnej oprogramowania na wieloprocesorach”. Materiały z dziewiątego sympozjum ACM SIGPLAN na temat zasad i praktyki programowania równoległego . PPoPP '03. s. 13–24. doi : 10.1145/781498.781501 .
•   Gotować, Jonathan J. (2002). „Odwrotne wykonanie kodu bajtowego Java” . Dziennik komputerowy . 45 (6): 608–619. CiteSeerX 10.1.1.20.4765 . doi : 10.1093/comjnl/45.6.608 .
• Chinony, Carlos Garcia; Madriles, Carlos; Sanchez, Jezus; Marcuello, Pedro; Gonzalez, Antonio; Tullsen, Dean M. (2005). „Kompilator mitozy: infrastruktura do wątków spekulacyjnych oparta na wycinkach przed obliczeniem” . Materiały z konferencji ACM SIGPLAN 2005 na temat projektowania i wdrażania języka programowania . PLDI '05. s. 269–279. doi : 10.1145/1065010.1065043 .
• Hu, Shiwen; Bhargava, Ravi; John, Lizy Kurian (2003). „Rola przewidywania wartości zwracanej w wykorzystywaniu równoległości na poziomie metody spekulacyjnej” (PDF) . JILP . 5 : 1–21.
• Kazi, Iffat H. (2000). Dynamicznie adaptacyjny model paralelizacyjny oparty na spekulacyjnej wielowątkowości (praca doktorska). Uniwersytet w Minnesocie. s. 1–188.
• Pickett, Christopher JF; Verbrugge, Clark (2005). „SableSpMT: platforma programowa do analizy wielowątkowości spekulacyjnej w Javie” . Materiały z 6. warsztatu ACM SIGPLAN-SIGSOFT na temat analizy programów dla narzędzi programistycznych i inżynierii . PASTA '05. s. 59–66. doi : 10.1145/1108792.1108809 .
• Pickett, Christopher JF; Verbrugge, Clark (2005). „Spekulacja poziomu wątków oprogramowania dla języka Java i środowiska maszyny wirtualnej” (PDF) . Materiały z 18. międzynarodowej konferencji na temat języków i kompilatorów do obliczeń równoległych . LCPC '05. LNCS. Tom. 4339. s. 304–318. doi : 10.1007/978-3-540-69330-7_21 .
• Porter, Lew; Choi, Bumyong; Tullsen, Dean M. (2009). „Mapowanie ścieżki od sprzętowej pamięci transakcyjnej do spekulacyjnej wielowątkowości”. 18. Międzynarodowa Konferencja na temat Architektur Równoległych i Technik Kompilacji . PAKT '09. s. 313–324. doi : 10.1109/PACT.2009.37 .
• Rundberg, Piotr; Stenstrom, Per (2001). „Oprogramowany system spekulacji zależności danych na poziomie wątków dla wieloprocesorów” (PDF) . JILP . 3 : 1–28.
•    Steffan, J. Gregory; Colohan, Christopher; Zhai, Antonia; Mowry, Todd C. (2005). „Podejście STAMPede do spekulacji na poziomie wątku” . Transakcje ACM w systemach komputerowych . 23 (3): 253–300. CiteSeerX 10.1.1.79.4317 . doi : 10.1145/1082469.1082471 . S2CID 10499545 ​​.
• Whaley, John; Kozyrakis, Christos (2005). „Heurystyka spekulatywnej paralelizacji opartej na profilach na poziomie metody”. Międzynarodowa konferencja na temat przetwarzania równoległego . ICPP 2005. s. 147–156. doi : 10.1109/ICPP.2005.44 .
•   Renau, Jose; Strauss, Karin; Ceze, Ludwik; Liu, Wei; Sarangi, Smruti; Tuck, James; Torrellas, Josep (2006). „Spekulacje na temat efektywności energetycznej wątków” (PDF) . IEEE mikro . 26 (1): 80–91. doi : 10.1109/MM.2006.11 . S2CID 206472480 .
• Yoshizoe, Kazuki; Matsumoto, Takashi; Hiraki, Kei (1998). „Spekulacyjne wykonywanie równoległe na maszynie JVM” . Warsztaty w Wielkiej Brytanii dotyczące HPNC . s. 1–20.
• Oancea, Cosmin E.; Mycroft, Alan; Harris, Tim (2009). „Lekka implementacja na miejscu do spekulacji na poziomie wątków oprogramowania” (PDF) . Materiały z dwudziestego pierwszego dorocznego sympozjum na temat równoległości w algorytmach i architekturach . SPAA '09. s. 1–10. doi : 10.1145/1583991.1584050 .