Какова правильная теоретическая модель для разработки алгоритмов для современных и будущих высокопроизводительных компьютеров

20

Этот вопрос похож на более общий вопрос о том, какова правильная теоретическая модель компьютера для разработки алгоритма и структур данных.
Здесь я задаю конкретный вопрос о современных высокопроизводительных компьютерах (например, тех, которые перечислены в списке 500 лучших ) или даже о предстоящие суперкомпьютеры.

Учитывая, что эти компьютеры обычно работают с огромными наборами данных (кажется, что некоторые люди используют такие машины в основном потому, что у них огромная объединенная основная память) аспекты модели ввода-вывода (представленной Аггарвалем и Виттером в 1988 году ) и ее параллельной версии , PEM ( Arge, Goodrich, Nelson и Sitchinava в 2008 году ) должны присутствовать. С другой стороны, должно быть что-то в связи, в частности, наказание сверхмалых пакетов всем остальным вычислительным узлам.

Как вы можете себе представить, я не боюсь, что у меня заканчиваются идеи при создании новой модели, но меня немного беспокоит, что я мог бы пропустить предыдущие попытки сделать это, в частности, потому что у меня сложилось впечатление, что годы 1980- В 1995 или около того было много таких попыток моделирования (таких как BSP или мостовые модели), которые, похоже, не получили широкого распространения.

На какие модели стоит присмотреться?

Рико Джейкоб
источник
это не отвечает вообще, но любая модель для текущих и будущих суперкомпьютеров, но встраивает отказы / отказоустойчивость.
Сильвен Пейроннет
Посмотрите на таксономию Флинна. Согласно Википедии, «все топ-10 и большинство суперкомпьютеров TOP500 основаны на архитектуре MIMD». en.wikipedia.org/wiki/MIMD
Мохаммед Аль-Туркистани
Можете ли вы уточнить предложение: «С другой стороны, должно быть что-то в связи, в частности, наказание сверхмалых пакетов всем остальным вычислительным узлам». это опечатка? это должно толкать ? может ли кто-нибудь ответить на этот вопрос параллельными моделями проектирования, например, mapreduce, CSP Хоара? см. также кеширование забытых алгоритмов, Википедия
vzn

Ответы:

9

На PODC 2009 Брюс Хендриксон выступил с феноменальным приглашенным докладом по этим вопросам. (Его слайды, кажется, не в сети, но вы можете спросить его, можете ли вы их увидеть.) Я не думаю, что есть «правильная» модель - бонус для вас! - но я бы посоветовал вам взглянуть на его статьи, особенно на странице « Графики и архитектуры» , где он пытается выяснить, как обрабатывать огромные графы с небольшой структурой (например, «современные» наборы данных) на многопоточных машинах.

Аарон Стерлинг
источник
Спасибо за указатель. Просматривая его, у меня сложилось впечатление, что он не столько определяет модель, которая позволила бы провести теоретический анализ. Я что-то упускаю? Возможно, мне следует связаться с ним напрямую.
Рико Джейкоб
@Riko Jacob: Я согласен, что Хендриксон больше практикующий, чем модельер. Я думал, что у него была превосходная интуиция для того, что было необходимо. Если вам нужны статьи о моделях, возможно, вас больше заинтересует семинар по теории и многоядерности . Однако я не нахожу ни одну из этих моделей удовлетворительной, и мне было бы очень интересно посмотреть, что вы придумали. :-)
Аарон Стерлинг
8

Одна неясная проблема - как будут развиваться кэши. Тезис 2009 года Никоса Хардавелласа рассматривает эти вещи с системной точки зрения, включая соображения физических ограничений для масштабируемых систем памяти. Тезис не представляет модель как таковую, но может дать вам некоторые подсказки.

Расмус Паг
источник
4

журналИкс

Суреш Венкат
источник
Просматривая его, он выглядит для меня как предшественник забытой в кэше модели. Я также не видел никаких идей о параллельной обработке. Я что-то здесь упустил?
Рико Джейкоб
Я думаю, что это больше о иерархических моделях памяти, это правда.
Суреш Венкат