Узи Вишкин

Материал из Циклопедии
Перейти к: навигация, поиск

Узи Вишкин

Web-Vishkin13 0.jpg
Дата рождения 1953
Место рождения Тель-Авив, Израиль













Узи Вишкин (англ. Uzi Vishkin) — израильский компьютерный учёный[1].

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

Родился в 1953 году в Тель-Авиве.

В 1974 году получил степень бакалавра, а затем и магистра по математике в Еврейском университете.

В 1981 году получил докторскую степень в области компьютерных наук в Технионе.

Затем год проработал в исследовательском центре IBM Thomas J. Watson в Йорктаун-Хайтс, Нью-Йорк.

В 1982—1984 годах работал на факультете информатики в Нью-Йоркском университете и оставался связанным с ним до 1988 года.

В 1984—1997 годах работал на факультете информатики в Тель-Авивском университете, в 1987—1988 годах — заведующий кафедрой.

В 1988 году вместе с Барухом Шибером разработал способ вычисления ближайших общих предков в произвольном (но фиксированном) ориентированном лесу с применением привлекательной и поучительной смеси битовых и алгоритмических методов. Шибер и Вишкин предварительно обрабатывали лес, отображая его вершины в скошенную пирамиду [math]S[/math] размером [math]n[/math] путем вычисления трех величин для каждой вершины [math]u[/math]. Алгоритм Баруха Шибера и Узи Вишкина для низшего общего предка вполне практичен для использования и программирования.

С 1988 года работает в Мэрилендском университете в Колледж-Парке.

В 1996 году был избран членом Ассоциации вычислительной техники.

В 2007 году будучи профессором Инженерного колледжа им. Джеймса Кларка, вместе со своими студентами создал прототип «школьного суперкомпьютера». В компьютере Explicit Multi-Threading разработанная десятки лет назад концепция использования алгоритмов параллельных вычислений была реализована с учетом возможностей, которые дает огромное число транзисторов, имеющихся в современных полупроводниковых устройствах. Таким образом, группа инженеров из Инженерной школы Джеймса Кларка под руководством профессора Узи Вишкина из Мерилендского университета создала прототип персональных компьютеров следующего поколения, способных производить вычисления в сотни раз быстрее ныне существующих систем. Секрет — в технологии параллельных вычислений на одном микропроцессоре, что означает, что такой чип может выполнять одновременно множество различных задач, тем самым значительно сокращая время вычислений. Вишкин, один из пионеров в области параллельного компьютинга, приступил к созданию параллельных алгоритмов еще в 1979 году. Над созданием данного прототипа, на котором можно было бы проверить его теорию, он работает с 1997 года. В декабре 2006 года его команда такой прототип создала. В созданном прототипе оригинальной архитектуры на площади обычного микропроцессора были смонтированы 64 параллельных процессора, причём так, что их программирование и разработка для них программного обеспечения не представляет особой проблемы.

Области исследований: параллельные вычислительные системы, параллельные алгоритмы ранжирования списков, наименьший общий предок, остовное дерево и шарнир (в теории графов).

В сфере раскраски графов (тема параллельные и распределённые алгоритмы) самым простым интересным случаем является n-цикл. Ричард Коул и Узи Вишкин показали, что существует распределённый алгоритм, который уменьшает количество цветов от n до [math]O(log(n))[/math], используя лишь один раз обмен сообщениями между соседями. Повторяя ту же процедуру, можно получить 3-раскраску n-цикла за [math]O(log^*(n))[/math] раундов связи (при условии, что даны уникальные идентификаторы узлов). Функция [math]log^*[/math], итерированный логарифм, является чрезвычайно медленно растущей функцией, «почти константа». Следовательно, результаты Коула и Вишкина поднимают вопрос о том, есть ли распределённый алгоритм 3-раскраски n-цикла, который выполняется за константное время. Натан Линиал показал, что это невозможно: любой детерминированный распределённый алгоритм требует [math]\Omega(log^*(n))[/math] раундов связи для уменьшения N-раскраски до 3-раскраски в n-цикле. Техника Коула и Вишкина также может быть применена для произвольного графа с ограниченной степенью вершин, в этом случае время работы составляет [math]P(\Delta) + O(log^*(n))[/math]. Этот метод был обобщен для графа единичных кругов Шнайдером и т. д.

[править] Труды

  • Shiloach, Yossi; Vishkin, Uzi (1982a), "An O(log n) parallel connectivity algorithm", Journal of Algorithms, 3: 57–67.
  • Shiloach, Yossi; Vishkin, Uzi (1982b), "An O(n2 log n) parallel max-flow algorithm", Journal of Algorithms, 3 (2): 128–146.
  • Mehlhorn, Kurt; Vishkin, Uzi (1984), "Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories", Acta Informatica, 21 (4): 339–374
  • Tarjan, Robert; Vishkin, Uzi (1985), "An efficient parallel biconnectivity algorithm", SIAM Journal on Computing, 14 (4): 862–874.
  • Vishkin, Uzi (1985), "Optimal parallel pattern matching in strings", Information and Control, 67 (1–3): 91–113.
  • Cole, Richard; Vishkin, Uzi (1986), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control, 70 (1): 32–53.
  • Vishkin, Uzi; Dascal, Shlomit; Berkovich, Efraim; Nuzman, Joseph (1998), "Explicit Multi-Threading (XMT) bridging models for instruction parallelism", Proc. 1998 ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 140–151.
  • Naishlos, Dorit; Nuzman, Joseph; Tseng, Chau-Wen; Vishkin, Uzi (2003), "Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach", Theory of Computer Systems, 36 (5): 551–552.
  • Wen, Xingzhi; Vishkin, Uzi (2008), "FPGA-based prototype of a PRAM-on-chip processor", Proc. 2008 ACM Conference on Computing Frontiers (Ischia, Italy), pp. 55–66.
  • Vishkin, Uzi (January 2011), "Using simple abstraction to reinvent computing for parallelism", Communications of the ACM, 54 (1): 75–85.
  • Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (February 2018), "Easy PRAM-Based High-Performance Parallel Programming with ICE", IEEE Transactions on Parallel and Distributed Systems, 29 (2): 377–390.

[править] Источники

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты