Узи Вишкин

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

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

Биография

Узи Вишкин родился в Тель-Авиве, Израиль. Он получил степень бакалавра наук. (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 году что количество транзисторов на кристалле, предусмотренное законом Мура, позволит построить мощный параллельный компьютер на одном кремниевом чипе в течение десятилетия. разработать свои алгоритмы для модели PRAM. Далее он изобрел явную многопоточную (XMT) компьютерную архитектуру, которая позволяет реализовать эту теорию PRAM, и привел свою исследовательскую группу к созданию в январе 2007 года 64-процессорного компьютера. по имени Паралип, это демонстрирует общую концепцию. Концепция 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-программирования для учащихся от старших классов до аспирантов.

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

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

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

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

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

• Шилоах, Йоси; Вишкин, Узи (1982a), « Алгоритм параллельной связности O (log n )», Journal of Algorithms , 3 : 57–67, doi : 10.1016/0196-6774(82)90008-6 .
• Шилоах, Йоси; Вишкин, Узи (1982б), «Ан О ( н ² 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 .

Ссылки

• Баасе, Сара; Ван Гелдер, Аллен (2000), Компьютерные алгоритмы: Введение в проектирование и анализ (Третье изд.), Аддисон-Уэсли, ISBN  978-0-201-61244-8
• Брент, Ричард П. (1974), «Параллельная оценка общих арифметических выражений», Journal of the 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 со ссылками на выпуск программного обеспечения, онлайн-учебник и материалы для обучения параллелизму .
• Узи Вишкин в ДБЛП .