Узи Вишкин

Израильско-американский ученый-компьютерщик

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

биография

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

PRAM-на-кристалле

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

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

В области параллельных алгоритмов Узи Вишкин стал соавтором статьи Шилоах и Вишкин (1982b), в которой предложена концепция рабочего времени (WT) (иногда называемая глубиной работы) для концептуализации и описания параллельных алгоритмов. Структура WT была принята в качестве базовой структуры представления в книгах по параллельным алгоритмам JaJa (1992) и Keller, Kessler & Traeff (2001), а также в классных заметках Вишкина (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.
• Шилоах, Йоси; Вишкин, Узи (1982b), « О ( n ²  log  n ) параллельный алгоритм максимального потока», Journal of Algorithms , 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.
• Тарьян, Роберт; Вишкин, Узи (1985), «Эффективный параллельный алгоритм двусвязности», SIAM Journal on Computing , 14 (4): 862–874, CiteSeerX  10.1.1.465.8898 , doi : 10.1137/0214061, S2CID  7231609.
• Вишкин, Узи (1985), «Оптимальное параллельное сопоставление с образцом в строках», Information and Control , 67 (1–3): 91–113, doi : 10.1016/S0019-9958(85)80028-0.
• Коул, Ричард; Вишкин, Узи (1986), «Детерминистическое подбрасывание монеты с применением оптимального ранжирования в параллельных списках», Information and Control , 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-on-chip на базе FPGA», Учеб. Конференция ACM по передовым технологиям вычислений 2008 г. (Искья, Италия) (PDF) , стр. 55–66, doi : 10.1145/1366230.1366240, ISBN 978-1-60558-077-7, S2CID  11557669.
• Вишкин, Узи (январь 2011 г.), «Использование простой абстракции для нового изобретения вычислений для параллелизма», Communications of the ACM , 54 (1): 75–85, doi : 10.1145/1866739.1866757, S2CID  10279904.
• Ганим, Фади; Вишкин, Узи; Баруа, Раджив (февраль 2018 г.), «Простое высокопроизводительное параллельное программирование на основе PRAM с ICE», Транзакции IEEE в параллельных и распределенных системах , 29 (2): 377–390, doi : 10.1109/TPDS.2017.2754376 , hdl : 1903 /18521.

Примечания

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

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

• Баасе, Сара; Ван Гелдер, Аллен (2000), Компьютерные алгоритмы: Введение в проектирование и анализ (Третье изд.), Аддисон-Уэсли, ISBN 978-0-201-61244-8
• Брент, Ричард П. (1974), «Параллельная оценка общих арифметических выражений», Журнал ACM , 21 (2): 201–208, doi : 10.1145/321812.321815 , S2CID  16416106.
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990), Введение в алгоритмы (первое издание), MIT Press и McGraw-Hill, ISBN 978-0-262-03141-7
• Эппштейн, Дэвид ; Галил, Цви (1988), «Параллельные алгоритмические методы для комбинаторных вычислений», Annu. Ред. Компьютер. наук. , 3 : 233–283, doi : 10.1146/annurev.cs.03.060188.001313

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

• Гольдберг, Эндрю В .; Плоткин, Серж А.; Шеннон, Грегори Э. (1988), «Параллельное нарушение симметрии в разреженных графах», SIAM Journal on Discrete Mathematics , 1 (4): 434–446, CiteSeerX  10.1.1.39.269 , doi : 10.1137/0401044
• ДжаДжа, Джозеф (1992), Введение в параллельные алгоритмы, Аддисон-Уэсли, 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), Введение в алгоритмы и творческий подход, Аддисон-Уэсли, ISBN 978-0-201-12037-0
• Вишкин, Узи (2009), Параллельное мышление: некоторые базовые алгоритмы и методы параллельного анализа данных, 104 страницы (PDF) , конспекты курсов по параллельным алгоритмам, преподаваемых с 1992 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технион
• Проект «Математическая генеалогия»: Узи Вишкин.
• ISI Web of Knowledge, высокоцитируемые исследователи: Узи Вишкин.

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

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