Явная многопоточность

Явная многопоточность ( XMT ) — это парадигма информатики для создания и программирования параллельных компьютеров, разработанных на основе параллельной вычислительной модели параллельной машины с произвольным доступом (PRAM). Более прямое объяснение XMT начинается с элементарной абстракции, которая сделала последовательные вычисления простыми: любая отдельная инструкция, доступная для выполнения в последовательной программе, выполняется немедленно. Следствием этой абстракции является пошаговое (индуктивное) объяснение команды, доступной следующей для выполнения. Элементарная параллельная абстракция, лежащая в основе XMT, получившая название «Немедленное одновременное выполнение» (ICE) у Вишкина (2011) , заключается в том, что неограниченное количество инструкций, доступных для одновременного выполнения, выполняются немедленно. Следствием ICE является пошаговое (индуктивное) объяснение инструкций, доступных следующим для одновременного выполнения. Выходя за рамки серийного компьютера фон Неймана (единственной успешной платформы общего назначения на сегодняшний день), XMT стремится к тому, чтобы информатика снова смогла дополнить математическую индукцию простой однострочной вычислительной абстракцией.

Машина с произвольным доступом (RAM) — это абстрактная модель машины, используемая в информатике для изучения алгоритмов и сложности стандартных последовательных вычислений. Вычислительная модель PRAM параллельных — это абстрактная модель параллельной машины, которая была введена для аналогичного изучения параллельных алгоритмов и сложности вычислений , когда они еще не были созданы. Исследователи накопили большой объем знаний о параллельных алгоритмах для модели PRAM. Эти параллельные алгоритмы также известны своей простотой по стандартам других подходов к параллельным алгоритмам.

Большой объем знаний о параллельных алгоритмах модели PRAM и их относительная простота побудили к созданию компьютеров, программирование которых может осуществляться с помощью этих параллельных алгоритмов. Поскольку производительность параллельных программистов уже давно считается решающим фактором успеха параллельного компьютера, простота алгоритмов имеет важное значение.

Многоядерные компьютеры построены на основе двух или более процессорных ядер, интегрированных в один кристалл интегральной схемы. Они широко используются во многих областях приложений, включая вычисления общего назначения.Явная многопоточность (XMT) — это вычислительная парадигма для создания и программирования многоядерных компьютеров с десятками, сотнями или тысячами процессорных ядер.

Экспериментальные работы, опубликованные в 2011 и 2012 годах, демонстрируют значительно большее ускорение передовых алгоритмов PRAM на прототипах XMT, чем при решении тех же задач на современных многоядерных компьютерах.

Работа, опубликованная в 2018 году, показывает, что параллельное программирование с фиксированным шагом (с использованием ICE) может достичь той же производительности, что и самый быстрый многопоточный код, настроенный вручную, в системах XMT. Такой подход с индуктивной синхронизацией отличается от подходов многопоточного программирования многих других базовых систем, которые известны требовательными программистами.

Парадигму XMT представил Узи Вишкин .

Основные уровни абстракции XMT

Парадигма вычислений с явной многопоточностью (XMT) объединяет несколько уровней абстракции.

Концепция рабочего времени (WT) (иногда называемая глубиной работы), предложенная Шилоахом и Вишкиным (1982) , обеспечивает простой способ концептуализации и описания параллельных алгоритмов. В рамках WT параллельный алгоритм сначала описывается в терминах параллельных раундов. Для каждого раунда описываются операции, которые необходимо выполнить, но некоторые проблемы можно скрыть. Например, не обязательно указывать количество операций в каждом раунде, не нужно упоминать процессоры и не нужно учитывать любую информацию, которая может помочь в распределении процессоров по заданиям. Во-вторых, предоставляется скрытая информация. Фактически, включение скрытой информации основано на доказательстве теоремы планирования, предложенной Брентом (1974) . Структура WT полезна, поскольку, хотя она может значительно упростить первоначальное описание параллельного алгоритма, вставка деталей, скрытых в этом первоначальном описании, часто не очень сложна. Например, структура WT была принята в качестве базовой структуры представления в книгах по параллельным алгоритмам (для модели PRAM). JaJa (1992) и Keller, Kessler & Traeff (2001) , а также в классных заметках Вишкина (2009) . Вишкин (2011) объясняет простую связь между структурой WT и более элементарной абстракцией ICE, отмеченной выше.

Парадигма XMT может быть запрограммирована с использованием XMTC , параллельного многопоточного языка программирования, который является небольшим расширением языка программирования C. Парадигма XMT включает рабочий процесс программиста, который начинается с приведения алгоритма в структуру WT и переходит к его программированию в ХМТС.

Многоядерные компьютерные системы XMT обеспечивают балансировку нагрузки многопоточных программ во время выполнения, используя несколько патентов. Один из них ^[1] обобщает концепцию счетчика программ , которая является центральной в архитектуре фон Неймана, на многоядерное оборудование.

Прототипирование XMT и ссылки на дополнительную информацию

В январе 2007 года 64-процессорный компьютер ^[2] по имени Паралип, ^[3] это демонстрирует, что общая концепция была завершена. Концепция XMT была представлена Vishkin et al. (1998) и Найшлос и др. (2003) и 64-процессорный компьютер XMT в Wen & Vishkin (2008) . Поскольку упрощение параллельного программирования является одной из самых больших задач, стоящих сегодня перед информатикой, демонстрация также была направлена на обучение основам алгоритмов PRAM и программирования XMTC учащихся начиная от старшеклассников Торберта и др. (2010 г.) в аспирантуру.

Об экспериментальной работе сообщается в Caragea & Vishkin (2011) по проблеме максимального потока и в двух статьях Эдвардса и Вишкина ( 2012a , 2012b ) по связности графов ( связность (теория графов) ), двусвязности графов ( двусвязный граф ) и трисвязности графов. Проблемы ( трехсвязного компонента ) продемонстрировали, что для некоторых из наиболее продвинутых алгоритмов в литературе по параллельным алгоритмам парадигма XMT может обеспечить ускорение от 8 до более чем 100 раз больше, чем для тех же задач на современных многоядерных компьютерах. . Каждое заявленное ускорение было получено путем сравнения тактовых циклов прототипа XMT с самым быстрым последовательным алгоритмом, работающим на самых быстрых последовательных машинах.

Кульминацией создания прототипа XMT стала работа Ганима, Вишкина и Баруа (2018) , установившая, что параллельное программирование с фиксированным шагом (с использованием ICE) может достичь той же производительности, что и самый быстрый многопоточный код, настроенный вручную, в системах XMT. Этот результат 2018 года обостряет контраст между программированием XMT и подходами к многопоточному программированию, используемыми почти во всех системах с другими ядрами, чьи условия гонки и другие требования имеют тенденцию бросать вызов, а иногда даже и подводить программистов Вишкин (2014) .

Ссылки

Брент, Ричард П. (1974), «Параллельная оценка общих арифметических выражений», Journal of the ACM , 21 (2): 201–208, CiteSeerX 10.1.1.100.9361 , doi : 10.1145/321812.321815 , S2CID 16416106 .
Шилоах, Иосия; Вишкин, Узи (1982), «Ан О ( н ² log n ) параллельный алгоритм максимального потока», Journal of Algorithms , 3 (2): 128–146, doi : 10.1016/0196-6774(82)90013-X .
ДжаДжа, Джозеф (1992), Введение в параллельные алгоритмы , Аддисон-Уэсли, ISBN 978-0-201-54856-3
Келлер, Йорг; Кесслер, Кристоф В.; Траефф, Джеспер Л. (2001), Практическое программирование PRAM , Wiley-Interscience, ISBN 978-0-471-35351-5
Найшлос, Дорит; Нузман, Джозеф; Ценг, Чау-Вэнь; Вишкин, Узи (2003), «К первому вертикальному прототипированию подхода к чрезвычайно детальному параллельному программированию» (PDF) , Теория вычислительных систем , 36 (5): 551–552, doi : 10.1007/s00224-003-1086 -6 , S2CID 1929495 .

Торберт, Шейн; Вишкин, Узи; Цур, Рон; Эллисон, Дэвид (2010), «Возможно ли обучение старшеклассников параллельному алгоритмическому мышлению?», Материалы 41-го технического симпозиума ACM по образованию в области компьютерных наук - SIGCSE '10 , стр. 290, номер домена : 10.1145/1734263.1734363 , ISBN 9781450300063 .
Вишкин, Узи; Даскаль, Шломит; Беркович, Эфраим; Нузман, Джозеф (1998), «Модели мостового соединения явной многопоточности (XMT) для параллелизма инструкций» , Proc. Симпозиум ACM 1998 года по параллельным алгоритмам и архитектурам (SPAA) , стр. 140–151 .
Вишкин, Узи (2009), Параллельное мышление: некоторые базовые алгоритмы и методы параллельного анализа данных, 104 страницы (PDF) , конспекты курсов по параллельным алгоритмам, преподаваемых с 1992 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технион
Вэнь, Синчжи; Вишкин, Узи (2008), «Прототип процессора PRAM-on-chip на базе FPGA», Proc. Конференция ACM 2008 г. по передовым технологиям вычислений (Искья, Италия) (PDF) , стр. 55–66, doi : 10.1145/1366230.1366240 , ISBN 9781605580777 , S2CID 11557669 .
Вишкин, Узи (2011), «Использование простой абстракции для нового изобретения вычислений для параллелизма», Communications of the ACM , 54 : 75–85, doi : 10.1145/1866739.1866757 .
Карагеа, Джордж; Вишкин, Узи (2011), «Краткое объявление: лучшее ускорение для параллельного максимального потока», Proc. 23-й симпозиум ACM по параллелизму в алгоритмах и архитектурах (SPAA) , стр. 131–134, doi : 10.1145/1989493.1989511 , ISBN 9781450307437 , S2CID 5511743 .
Эдвардс, Джеймс А.; Вишкин, Узи (2012a), «Лучшее ускорение с использованием более простого параллельного программирования для связности графов и двусвязности», Труды Международного семинара 2012 года по моделям программирования и приложениям для многоядерных и многоядерных процессоров , стр. 103–114, doi : 10.1145/2141702.2141714 , ISBN 9781450312110 , S2CID 15095569 .
Эдвардс, Джеймс А.; Вишкин, Узи (2012b), «Краткое объявление: ускорение трисвязности параллельных графов», Учеб. 24-й симпозиум ACM по параллелизму в алгоритмах и архитектурах (SPAA) , стр. 190–192, doi : 10.1145/2312005.2312042 , ISBN 9781450312134 , S2CID 16908459 .
Вишкин, Узи (2014), «Не работает ли многоядерное оборудование для параллельной обработки общего назначения? Точка зрения статьи», Communications of the ACM , 57 (4): 35–39, doi : 10.1145/2580945 , S2CID 30098719 .
Ганим, Фади; Вишкин, Узи; Баруа, Раджив (февраль 2018 г.), «Простое высокопроизводительное параллельное программирование на основе PRAM с ICE», Транзакции IEEE в параллельных и распределенных системах , 29 (2): 377–390, doi : 10.1109/TPDS.2017.2754376 , hdl : 1903 /18521 .

Примечания

^ Вишкин, Узи. Архитектура набора команд Spawn-join для обеспечения явной многопоточности. Патент США 6463527. См. также Вишкин и др. (1998) .
^ Университет Мэриленда, пресс-релиз, 26 июня 2007 г.: «Профессор из Мэриленда создает настольный суперкомпьютер». Архивировано 14 декабря 2009 г. в Wayback Machine .
^ Университет Мэриленда, Инженерная школа А. Джеймса Кларка, пресс-релиз, 28 ноября 2007 г.: «Следующий большой «скачок» в вычислительных технологиях получает имя» .

Внешние ссылки

Домашняя страница проекта XMT со ссылками на выпуск программного обеспечения, онлайн-учебник и материалы для обучения параллелизму .

[1] Вишкин, Узи. Архитектура набора команд Spawn-join для обеспечения явной многопоточности. Патент США 6463527. См. также Вишкин и др. (1998) .

[2] Университет Мэриленда, пресс-релиз, 26 июня 2007 г.: «Профессор из Мэриленда создает настольный суперкомпьютер». Архивировано 14 декабря 2009 г. в Wayback Machine .

[3] Университет Мэриленда, Инженерная школа А. Джеймса Кларка, пресс-релиз, 28 ноября 2007 г.: «Следующий большой «скачок» в вычислительных технологиях получает имя» .

[1]

[2]

[3]