Jaki jest właściwy model teoretyczny do projektowania algorytmów dla obecnych i przyszłych komputerów o wysokiej wydajności

To pytanie jest podobne do bardziej ogólnego pytania dotyczącego tego, jaki jest właściwy model teoretyczny komputera do projektowania algorytmów i struktur danych.
Tutaj pytam konkretnie o obecne komputery o wysokiej wydajności (takie jak te wymienione na liście 500 najlepszych ), a nawet o nadchodzące superkomputery.

Biorąc pod uwagę, że komputery te zwykle pracują na ogromnych zestawach danych (wydaje się, że niektórzy ludzie używają takich maszyn głównie dlatego, że mają ogromną połączoną pamięć główną) aspektów modelu I / O (wprowadzonego przez Aggarwal i Vitter w 1988 r. ) I jego równoległej wersji , PEM ( Arge, Goodrich, Nelson i Sitchinava w 2008 r. ) powinien być obecny. Z drugiej strony, powinno być coś o komunikacji, w szczególności karanie bardzo małych pakietów do wszystkich innych węzłów obliczeniowych.

Jak możesz sobie wyobrazić, nie obawiam się, że przy tworzeniu nowego modelu zabrakło mi pomysłów, ale trochę się martwię, że mógłbym przeoczyć poprzednie próby, szczególnie dlatego, że mam wrażenie, że lata 1980- Około 1995 roku miało miejsce wiele takich prób modelowania (takich jak BSP lub modele pomostowe), które wydają się nie być szeroko stosowane.

Jakie modele powinienem przyjrzeć się bliżej?

Na PODC 2009 Bruce Hendrickson wygłosił fenomenalne zaproszenie na te tematy. (Jego slajdy nie wydają się być w trybie online, ale możesz zapytać go, czy możesz je zobaczyć.) Nie sądzę, że istnieje jeszcze „odpowiedni” model - premia dla Ciebie! - ale proponuję spojrzeć na jego artykuły, szczególnie te na stronie Wykresy i architektury , gdzie próbuje dowiedzieć się, jak obsługiwać ogromne wykresy o małej strukturze (tj. „nowoczesne” zbiory danych) na maszynach wielowątkowych.

Jedną z niejasnych kwestii jest to, jak będą się rozwijać pamięci podręczne. Teza Nikosa Hardavellasa z 2009 r. Traktuje te kwestie z perspektywy systemowej, w tym rozważań na temat fizycznych ograniczeń skalowalnych systemów pamięci. Teza nie przedstawia modelu jako takiego, ale może dać ci pewne wskazówki.

Jednym z modeli, który ładnie uchwycił modele hierarchiczne (pomyśl o rdzeniach lokalnych, wspólnej pamięci na chipie i pamięci globalnej) jest artykuł STOC 87 autorstwa Aggarwal i in . Nie sądzę, żeby kiedykolwiek miała przyczepność, ale stanowi ciekawą lekturę. Główną ideą jest to, że dostęp do lokalizacji pamięci x wymaga czasu .$\lceil \log x\rceil$