Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Явная многопоточность ( XMT ) - это парадигма информатики для создания и программирования параллельных компьютеров, спроектированных на основе параллельной вычислительной модели параллельной машины с произвольным доступом (PRAM). Более прямое объяснение XMT начинается с элементарной абстракции, которая упростила последовательные вычисления : любая отдельная инструкция, доступная для выполнения в последовательной программе, выполняется немедленно. Следствием этой абстракции является пошаговая (индуктивная) экспликация инструкции, доступной следующей для выполнения. Элементарная параллельная абстракция, лежащая в основе XMT, названная в Вишкине (2011) Immediate Concurrent Execution (ICE ), заключается в том, что неограниченное количество инструкций, доступных для одновременного выполнения, выполняется немедленно. Следствием 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) , а также в заметках для занятий Vishkin (2009) . Вишкин (2011) объясняет простую связь между фреймворком WT и более элементарной абстракцией ICE, упомянутой выше.

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

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

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

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

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

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

Ссылки [ править ]

  • Брент, Ричард П. (1974), «Параллельное вычисление общих арифметических выражений», Журнал ACM , 21 (2): 201–208, CiteSeerX  10.1.1.100.9361 , doi : 10.1145 / 321812.321815.
  • Шилоах, Йосси; Vishkin, Узи (1982), "О О ( п 2  журнала  п ) параллельный алгоритм Макс-поток", журнал алгоритмы , 3 (2): 128-146, DOI : 10.1016 / 0196-6774 (82) 90013-X.
  • JaJa, Джозеф (1992), Введение в параллельные алгоритмы , Addison-Wesley, 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.
  • Торберт, Шейн; Вишкин, Узи; Цур, Рон; Эллисон, Дэвид (2010), «Возможно ли обучение учащихся старших классов параллельному алгоритмическому мышлению?», Материалы 41-го технического симпозиума ACM по образованию в области компьютерных наук - SIGCSE '10 , стр. 290, DOI : 10,1145 / 1734263,1734363 , ISBN 9781450300063.
  • Вишкин, Узи; Даскаль, Шломит; Беркович, Ефраим; Нузман, Джозеф (1998), "Явные модели многопоточности (XMT) мостов для параллелизма команд" , Proc. Симпозиум ACM 1998 г. по параллельным алгоритмам и архитектурам (SPAA) , стр. 140–151.
  • Вишкин, Узи (2009 г.), « Мышление параллельно: некоторые базовые алгоритмы и методы параллельного обмена данными с данными», 104 страницы (PDF) , конспекты курсов по параллельным алгоритмам, преподаваемым с 1992 г. в Университете Мэриленда, Колледж-Парк, Тель-Авивском университете и Технион CS1 maint: обескураженный параметр ( ссылка )
  • Вэнь, Синчжи; Вишкин, Узи (2008), "Прототип процессора PRAM на кристалле на основе FPGA", Proc. 2008 ACM Конференция по Вычислительной Frontiers (Ischia, Италия) (PDF) . С. 55-66, DOI : 10,1145 / 1366230,1366240 , ISBN 9781605580777.
  • Vishkin, Узи (2011), "Использование простой абстракции изобрести вычисления для параллелизма", коммуникаций ACM , 54 : 75-85, DOI : 10,1145 / 1866739.1866757.
  • Караджа, Джордж; Вишкин, Узи (2011), «Краткое сообщение: улучшение ускорения для параллельного max-flow», Proc. Двадцать третий ACM симпозиум по параллельности в алгоритмах и архитектурах (SPAA) , С. 131-134,. DOI : 10,1145 / 1989493,1989511 , ISBN 9781450307437.
  • Эдвардс, Джеймс А .; Вишкин, Узи (2012), «Повышение скорости с использованием более простого параллельного программирования для связности графов и двусвязности», Труды Международного семинара 2012 года по моделям программирования и приложениям для многоядерных и многоядерных процессоров , стр. 103–114, doi : 10.1145 / 2141702.2141714 , ISBN 9781450312110.
  • Эдвардс, Джеймс А .; Вишкин, Узи (2012), "Краткое сообщение: ускорение трехсвязности параллельных графов", Proc. 24 - е ACM симпозиум по Параллельности в алгоритмах и архитектурах (SPAA) , стр 190-192,. DOI : 10,1145 / 2312005,2312042 , ISBN 9781450312134.
  • Вишкин, Узи (2014), «Не работает ли многоядерное оборудование для параллельной обработки общего назначения? Точка зрения статьи», Коммуникации ACM , 57 (4): 35–39, doi : 10.1145 / 2580945.
  • Ганим, Фади; Вишкин, Узи; Баруа, Раджив (февраль 2018), "Easy PRAM-Based Высокопроизводительные Параллельное программирование с ICE", IEEE Transactions по параллельным и распределенным системам , 29 (2): 377-390, DOI : 10,1109 / TPDS.2017.2754376 , ЛВП : 1903 / 18521.

Заметки [ править ]

  1. ^ Vishkin, Узи. Архитектура набора инструкций spawn-join для обеспечения явной многопоточности. Патент США 6,463,527. См. Также Вишкин и др. (1998) .
  2. ^ Университет Мэриленда, пресс-релиз, 26 июня 2007 г .: «Профессор Мэриленда создает настольный суперкомпьютер» .
  3. ^ Университет Мэриленда, инженерная школа А. Джеймса Кларка, пресс-релиз, 28 ноября 2007 г .: «Следующий большой« скачок »в вычислительной технике получает имя» .

Внешние ссылки [ править ]

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