Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Узи Вишкин
Родившийся1953 г.
Тель-Авив, Израиль
Альма-матерЕврейский университет
Технион
Научная карьера
Поляпараллельные алгоритмы
УчрежденияIBM Исследовательский центр Томаса Дж. Ватсона
Нью-Йоркский университет
Тель-Авивский университет
Мэрилендский университет, Колледж-Парк
ДокторантЙоси Шилоах
ВлиянияРоберт Ауманн , главный советник

Узи Вишкин (родился в 1953 г.) - специалист по информатике в Мэрилендском университете в Колледж-Парке , где он является профессором электротехники и вычислительной техники в Институте передовых компьютерных исследований Мэрилендского университета (UMIACS). Узи Вишкин известен своими работами в области параллельных вычислений . В 1996 годе он был введен в качестве стипендиата от Ассоциации вычислительной техники , со следующей цитатой: «Один из пионеров параллельных алгоритмов исследуют, семенной вклад доктора Vishkin играл ведущую роль в формировании и формирования , что мышление параллельно пришло иметь в виду в фундаментальной теории информатики ". [1]

Биография [ править ]

Узи Вишкин родился в Тель-Авиве, Израиль. Он получил степень бакалавра наук. (1974) и M.Sc. получил степень бакалавра математики в Еврейском университете , прежде чем получить докторскую степень. Кандидат компьютерных наук в Технионе (1981). Затем он проработал год в исследовательском центре IBM Thomas J. Watson Research Center в Йорктаун-Хайтс, штат Нью-Йорк. С 1982 по 1984 год он работал на факультете информатики Нью-Йоркского университета и оставался связанным с ним до 1988 года. С 1984 по 1997 год он работал на факультете информатики Тель-Авивского университета, занимая должность его председателя с 1987 по 1988 год. С 1988 года он работает в Мэрилендском университете в Колледж-Парке .

PRAM-on-chip [ править ]

Примечательная элементарная абстракция, заключающаяся в том, что любая отдельная инструкция, доступная для выполнения в последовательной программе, выполняется немедленно, упростила последовательные вычисления. Следствием этой абстракции является пошаговая (индуктивная) экспликация инструкции, доступной следующей для выполнения. Элементарная параллельная абстракция, лежащая в основе концепции PRAM-on-chip, получившая название Immediate Concurrent Execution (ICE) у Вишкина (2011), заключается в том, что неограниченное количество инструкций, доступных для одновременного выполнения, выполняется немедленно. Следствием ICE является пошаговая (индуктивная) экспликация (также известная как шаг блокировки) инструкций, доступных для одновременного выполнения. Выходя за рамки серийного компьютера фон Неймана (единственной успешной платформы общего назначения на сегодняшний день), концепция PRAM-on-chip заключается в том, что информатика снова сможет дополнить математическую индукцию простой абстракцией однострочных вычислений. Далее следует хронологический обзор эволюции концепции PRAM-on-chip и ее аппаратного и программного обеспечения . В 1980-х и 1990-х годах Узи Вишкин был соавтором нескольких статей, которые помогли построить теорию параллельных алгоритмов в математической модели, называемойпараллельная машина с произвольным доступом (PRAM), которая является обобщением для параллельных вычислений стандартной машины с произвольным доступом (RAM) модели последовательных вычислений. Параллельные машины, необходимые для реализации модели PRAM, в то время еще не были построены, и многие из них не смогли создать такие машины. Заканчивая в 1997 году [2] , что число транзисторов на кристалле , как следует из закона Мура позволит строить мощный параллельный компьютер на одном кристалле кремния в течение десяти лет, он разработал PRAM-On-Chip видение, призывающие для построения параллельного компьютера на единый чип, который позволяет программистам разрабатывать свои алгоритмы для модели PRAM. Он продолжил изобретать явное многопоточное(XMT) компьютерная архитектура, которая позволяет реализовать эту теорию PRAM, и привела его исследовательскую группу к завершению в январе 2007 года 64-процессорного компьютера [3], названного Paraleap, [4], который демонстрирует общую концепцию. Концепция XMT была представлена ​​в Vishkin et al. (1998) , Naishlos et al. (2003) , 64-процессорный компьютер XMT в Wen & Vishkin (2008) , в Vishkin (2011) и совсем недавно в Ghanim, Vishkin & Barua (2018), где было показано, что параллельное программирование с синхронизацией по шагам (с использованием ICE) может обеспечить такую ​​же производительность, как и самый быстрый настраиваемый вручную многопоточный код в системах XMT. Такой индуктивный подход с блокировкой шага контрастирует с подходами многопоточного программирования других многих основных систем, которые известны сложным программистам. Демонстрация XMT включала несколько аппаратных и программных компонентов, а также обучение алгоритмам PRAM для программирования XMT Paraleap с использованием языка под названием XMTC . Поскольку упростить параллельное программирование - одна из самых серьезных проблем, с которыми сегодня сталкивается компьютерная наука, демонстрация также стремилась включить обучение основам алгоритмов PRAM и программирования XMTC для учащихся, от средней школы до аспирантуры.

Параллельные алгоритмы [ править ]

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

В области параллельных и распределенных алгоритмов одной из основополагающих статей, написанных в соавторстве с Узи Вишкиным, является Cole & Vishkin (1986) . В этой работе был представлен эффективный параллельный метод раскраски графов . Алгоритм Коула – Вишкина находит раскраску вершин за n - цикл за O (log *  n ) циклов синхронной связи. Этот алгоритм в настоящее время представлен во многих учебниках, включая Введение в алгоритмы Кормена и др. [5], и он составляет основу многих других распределенных алгоритмов раскраски графов. [6]

Другие работы Узи Вишкина и различных соавторов включают параллельные алгоритмы для ранжирования списков , наименьшего общего предка , остовных деревьев и двусвязных компонентов .

Избранные публикации [ править ]

  • Шилоах, Йосси; Вишкин, Узи (1982a), « Алгоритм параллельного соединения O (log  n )», Журнал алгоритмов , 3 : 57–67, DOI : 10.1016 / 0196-6774 (82) 90008-6.
  • Шилоах, Йосси; Vishkin, Узи (1982b), "О О ( п 2  журнала  п ) параллельный алгоритм Макс-поток", журнал алгоритмы , 3 (2): 128-146, DOI : 10.1016 / 0196-6774 (82) 90013-X.
  • Мельхорн, Курт; Вишкин, Узи (1984), "Рандомизированное и детерминированное моделирование PRAM параллельными машинами с ограниченной степенью детализации параллельной памяти", Acta Informatica , 21 (4): 339–374, doi : 10.1007 / BF00264615 , S2CID  29789494.
  • Тарджан, Роберт; Vishkin, Узи (1985), "Алгоритм эффективного параллельного biconnectivity", SIAM журнал по вычислениям , 14 (4): 862-874, CiteSeerX  10.1.1.465.8898 , DOI : 10,1137 / 0214061.
  • Vishkin, Узи (1985), "Оптимальное параллельное сопоставление с образцом в строках", информации и управления , 67 (1-3): 91-113, DOI : 10.1016 / S0019-9958 (85) 80028-0.
  • Коул, Ричард; Vishkin, Узи (1986), "Детерминированная монета бросание с приложениями к оптимальному списку параллельного рейтинга", информация и управление , 70 (1): 32-53, DOI : 10.1016 / S0019-9958 (86) 80023-7.
  • Вишкин, Узи; Даскаль, Шломит; Беркович, Ефраим; Нузман, Джозеф (1998), "Явные мостовые модели многопоточности (XMT) для параллелизма команд" , Proc. Симпозиум ACM 1998 г. по параллельным алгоритмам и архитектурам (SPAA) , стр. 140–151.
  • Найшлос, Дорит; Нузман, Джозеф; Ценг, Чау-Вэнь; Вишкин, Узи (2003), «К первому вертикальному прототипу чрезвычайно детализированного подхода к параллельному программированию» (PDF) , Теория вычислительных систем , 36 (5): 551–552, DOI : 10.1007 / s00224-003-1086 -6 , S2CID  1929495.
  • Вэнь, Синчжи; Вишкин, Узи (2008), "Прототип процессора PRAM на кристалле на основе FPGA", Proc. 2008 ACM Конференция по Вычислительной Frontiers (Ischia, Италия) (PDF) . С. 55-66, DOI : 10,1145 / 1366230,1366240 , ISBN 978-1-60558-077-7, S2CID  11557669.
  • Vishkin, Узи (январь 2011), "Использование простой абстракции изобрести вычисления для параллелизма", коммуникаций ACM , 54 (1): 75-85, DOI : 10,1145 / 1866739,1866757.
  • Ганим, Фади; Вишкин, Узи; Баруа, Раджив (февраль 2018), "Easy PRAM-Based Высокопроизводительные Параллельное программирование с ICE", IEEE Transactions по параллельным и распределенным системам , 29 (2): 377-390, DOI : 10,1109 / TPDS.2017.2754376 , ЛВП : 1903 / 18521.

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

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

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

  • Баасе, Сара; Ван Гелдер, Аллен (2000), Введение в компьютерные алгоритмы для проектирования и анализа (третье издание), Addison-Wesley, ISBN 978-0-201-61244-8
  • Brent, Ричард П. (1974), "Параллельная оценка общих арифметических выражений", Журнал ACM , 21 (2): 201-208, DOI : 10,1145 / 321812,321815 , S2CID  16416106.
  • Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990), Введение в алгоритмы (первое издание), MIT Press и McGraw-Hill, ISBN 978-0-262-03141-7 CS1 maint: обескураженный параметр ( ссылка )
  • Эпштейн, Дэвид ; Галил, Цви (1988), "Параллельные алгоритмические методы комбинаторных вычислений", Annu. Rev. Comput. Sci. , 3 : 233-283, DOI : 10,1146 / annurev.cs.03.060188.001313

В этой обзорной статье цитируются 16 статей в соавторстве с Вишкиным.

  • Гольдберг, Эндрю В .; Плоткин, Серж А .; Шеннона, Грегори Е. (1988), "Параллельный нарушения симметрии в разреженных графов", SIAM журнал по дискретной математике , 1 (4): 434-446, CiteSeerX  10.1.1.39.269 , DOI : 10,1137 / 0401044
  • JaJa, Джозеф (1992), Введение в параллельные алгоритмы , Addison-Wesley, ISBN 978-0-201-54856-3

Цитирует 36 статей в соавторстве с Вишкиным.

  • Карп, Ричард М .; Рамачандран, Виджая (1988), «Обзор параллельных алгоритмов для машин с общей памятью», Калифорнийский университет, Беркли, Отдел EECS, Tech. Реп. UCB / CSD-88-408

В этом обзоре цитируется 20 статей в соавторстве с Вишкиным.

  • Келлер, Йорг; Кесслер, Кристоф В .; Трафф, Джеспер Л. (2001), Практическое программирование PRAM , Wiley-Interscience, ISBN 978-0-471-35351-5

Цитирует 19 статей в соавторстве с Вишкиным.

  • Манбер, Уди (1989), Введение в алгоритмы творческого подхода , Addison-Wesley, ISBN 978-0-201-12037-0 CS1 maint: обескураженный параметр ( ссылка )
  • Вишкин, Узи (2009), « Мышление параллельно: некоторые базовые алгоритмы и методы параллельного обмена данными», 104 страницы (PDF) , конспекты курсов по параллельным алгоритмам, которые преподаются с 1992 года в Университете Мэриленда, Колледж-Парк, Тель-Авивском университете и Технион
  • Математическая генеалогия Проект: Узи Вишкин .
  • ISI Web of Knowledge, авторитетные исследователи: Узи Вишкин .

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

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