Явная многопоточность - Explicit multi-threading
Явная многопоточность (XMT) это Информатика парадигма для создания и программирования параллельных компьютеров, разработанных на основе параллельная машина с произвольным доступом (PRAM) параллельная вычислительная модель. Более прямое объяснение XMT начинается с элементарной абстракции, которая сделала последовательные вычисления просто: любая отдельная инструкция, доступная для выполнения в последовательной программе, выполняется немедленно. Следствием этой абстракции является пошаговая (индуктивная) экспликация инструкции, следующей для выполнения. Элементарная параллельная абстракция за XMT, получившая название Immediate Concurrent Execution (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) и Келлер, Кесслер и Трафф (2001), а также в классных заметках Вишкин (2009). Вишкин (2011) объясняет простую связь между фреймворком WT и более элементарной абстракцией ICE, упомянутой выше.
Парадигма XMT может быть запрограммирована с использованием XMTC, параллельный многопоточный язык программирования, который является небольшим расширением языка программирования C. Парадигма XMT включает рабочий процесс программиста, который начинается с приведения алгоритма в структуру WT и переходит к его программированию в XMTC.
Многоядерные компьютерные системы XMT обеспечивают балансировку нагрузки во время выполнения многопоточных программ, включая несколько патентов. Один из них [1] обобщает счетчик команд концепция, которая занимает центральное место в фон Неймана архитектура к многоядерному оборудованию.
Прототипирование XMT и ссылки на дополнительную информацию
В январе 2007 г. 64-процессорный компьютер [2] названный Paraleap[3] что демонстрирует, что общая концепция была завершена. Концепция XMT была представлена в Вишкин и др. (1998) и Naishlos et al. (2003) и 64-процессорный компьютер XMT в Вен и Вишкин (2008). Поскольку упростить параллельное программирование - одна из самых больших проблем, с которыми сегодня сталкивается компьютерная наука, демонстрация также стремилась включить обучение основам алгоритмов PRAM и программирования XMTC для учащихся, начиная с средней школы. Torbert et al. (2010) закончить школу.
Экспериментальная работа опубликована в Карага и Вишкин (2011) для Задача максимального расхода, и в двух статьях Эдвардс и Вишкин (2012) для графической связи (Связность (теория графов) ), Биконность графа (двусвязный граф ) и трехсвязность графов (Трехкомпонентный компонент ) проблемы продемонстрировали, что для некоторых из наиболее продвинутых алгоритмов в литературе по параллельной алгоритмической деятельности парадигма XMT может предложить от 8 до более чем 100 раз большее ускорение, чем для тех же задач на современных многоядерных компьютерах. Каждое заявленное ускорение было получено путем сравнения тактовых циклов на прототипе XMT относительно самого быстрого последовательного алгоритма, работающего на самых быстрых последовательных машинах.
Создание прототипа XMT завершилось Ганим, Вишкин и Баруа (2018), установив, что параллельное программирование с синхронизацией шага (с использованием ICE) может обеспечить такую же производительность, как и самый быстрый настраиваемый вручную многопоточный код в системах XMT. Этот результат 2018 года усиливает контраст между программированием XMT и подходами к многопоточному программированию, используемыми почти во всех других многоядерных системах, чьи условия гонки и другие требования имеют тенденцию бросать вызов программистам, а иногда даже подводить Вишкин (2014).
Рекомендации
- Брент, Ричард П. (1974), "Параллельное вычисление общих арифметических выражений", Журнал ACM, 21 (2): 201–208, CiteSeerX 10.1.1.100.9361, Дои:10.1145/321812.321815.
- Шилоах, Йосси; Вишкин, Узи (1982), "Ан О(п2 бревноп) параллельный алгоритм максимального потока », Журнал алгоритмов, 3 (2): 128–146, Дои:10.1016 / 0196-6774 (82) 90013-X.
- JaJa, Джозеф (1992), Введение в параллельные алгоритмы, Эддисон-Уэсли, ISBN 978-0-201-54856-3
- Келлер, Йорг; Кесслер, Кристоф В .; Трафф, Джеспер Л. (2001), Практическое программирование PRAM, Wiley-Interscience, ISBN 978-0-471-35351-5
- Найшлос, Дорит; Нузман, Джозеф; Ценг, Чау-Вэнь; Вишкин, Узи (2003), «На пути к первому вертикальному прототипу чрезвычайно детализированного подхода к параллельному программированию» (PDF), Теория компьютерных систем, 36 (5): 551–552, Дои:10.1007 / s00224-003-1086-6.
- Торберт, Шейн; Вишкин, Узи; Цур, Рон; Эллисон, Дэвид (2010), «Возможно ли обучение учащихся старших классов параллельному алгоритмическому мышлению?», Материалы 41-го технического симпозиума ACM по образованию в области компьютерных наук - SIGCSE '10, п. 290, г. Дои:10.1145/1734263.1734363, ISBN 9781450300063.
- Вишкин, Узи; Даскаль, Шломит; Беркович, Ефраим; Нузман, Джозеф (1998), «Явные мостовые модели многопоточности (XMT) для параллелизма команд», Proc. 1998 Симпозиум ACM по параллельным алгоритмам и архитектурам (SPAA), стр. 140–151.
- Вишкин, Узи (2009), Параллельное мышление: некоторые основные алгоритмы и методы работы с параллельными данными, 104 страницы (PDF), Заметки о курсах курсов по параллельным алгоритмам, преподаваемых с 1992 года в Мэрилендском университете, Колледж-Парке, Тель-Авивском университете и Технионе.
- Вэнь, Синчжи; Вишкин, Узи (2008), "Прототип процессора PRAM на кристалле на основе FPGA", Proc. 2008 ACM Conference on Computing Frontiers (Искья, Италия) (PDF), стр. 55–66, Дои:10.1145/1366230.1366240, ISBN 9781605580777.
- Вишкин, Узи (2011), «Использование простой абстракции для переосмысления вычислений для параллелизма», Коммуникации ACM, 54: 75–85, Дои:10.1145/1866739.1866757.
- Караджа, Джордж; Вишкин, Узи (2011), «Краткое сообщение: улучшение ускорения для параллельного макс-потока», Proc. 23-й симпозиум ACM по параллелизму в алгоритмах и архитектурах (SPAA), стр. 131–134, Дои:10.1145/1989493.1989511, ISBN 9781450307437.
- Эдвардс, Джеймс А .; Вишкин, Узи (2012), «Повышение скорости за счет более простого параллельного программирования для связности графов и двусвязности», Труды Международного семинара 2012 года по моделям программирования и приложениям для многоядерных и многоядерных процессоров, стр. 103–114, Дои:10.1145/2141702.2141714, ISBN 9781450312110.
- Эдвардс, Джеймс А .; Вишкин, Узи (2012), "Краткое сообщение: ускорение трехсвязности параллельных графов", Proc. 24-й симпозиум ACM по параллелизму в алгоритмах и архитектурах (SPAA), стр. 190–192, Дои:10.1145/2312005.2312042, ISBN 9781450312134.
- Вишкин, Узи (2014), "Не работает ли многоядерное оборудование для параллельной обработки общего назначения? Точка зрения статьи", Коммуникации ACM, 57 (4): 35–39, Дои:10.1145/2580945.
- Ганим, Фади; Вишкин, Узи; Баруа, Раджив (февраль 2018 г.), «Простое высокопроизводительное параллельное программирование на основе PRAM с помощью ICE», Транзакции IEEE в параллельных и распределенных системах, 29 (2): 377–390, Дои:10.1109 / TPDS.2017.2754376, HDL:1903/18521.
Примечания
- ^ Вишкин, Узи. Архитектура набора инструкций spawn-join для обеспечения явной многопоточности. Патент США 6,463,527. Смотрите также Вишкин и др. (1998).
- ^ Университет Мэриленда, пресс-релиз, 26 июня 2007 г .: «Профессор из Мэриленда создает настольный суперкомпьютер».
- ^ Университет Мэриленда, инженерная школа А. Джеймса Кларка, пресс-релиз, 28 ноября 2007 г .: "Следующий большой" скачок "в вычислительной технике получил название".