Узи Вишкин - Uzi Vishkin

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

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

биография

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

PRAM-на-чипе

Примечательная элементарная абстракция, заключающаяся в том, что любая отдельная инструкция, доступная для выполнения в последовательной программе, выполняется немедленно, упростила последовательные вычисления. Следствием этой абстракции является пошаговая (индуктивная) экспликация инструкции, доступной следующей для выполнения. Элементарная параллельная абстракция, лежащая в основе концепции 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 была представлена ​​в Вишкин и др. (1998), Naishlos et al. (2003), 64-процессорный компьютер XMT в Вен и Вишкин (2008), в Вишкин (2011) и совсем недавно в Ганим, Вишкин и Баруа (2018), где было показано, что параллельное программирование с синхронизацией по шагам (с использованием ICE) может достигать той же производительности, что и самый быстрый настраиваемый вручную многопоточный код в системах XMT. Такой индуктивный подход с блокировкой шага контрастирует с подходами многопоточного программирования других многих основных систем, которые известны сложным программистам. Демонстрация XMT включала несколько аппаратных и программных компонентов, а также обучение алгоритмам PRAM для программирования XMT Paraleap с использованием языка, называемого XMTC. Поскольку упростить параллельное программирование - одна из самых серьезных проблем, с которыми сегодня сталкивается компьютерная наука, демонстрация также была направлена ​​на обучение основам алгоритмов PRAM и программирования XMTC учащимся от старших классов до аспирантов.

Параллельные алгоритмы

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

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

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

Избранные публикации

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

Примечания

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

Рекомендации

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

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

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

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

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

внешняя ссылка