Uzi Vishkin - Uzi Vishkin

Uzi Vishkin
narozený1953
Tel Aviv, Izrael
Alma materHebrejská univerzita
Technion
Vědecká kariéra
Poleparalelní algoritmy
InstituceIBM Thomas J. Watson Research Center
Newyorská univerzita
Tel Avivská univerzita
University of Maryland, College Park
Doktorský poradceYossi Shiloach
VlivyRobert Aumann, Hlavní poradce

Uzi Vishkin (narozen 1953) je počítačový vědec na University of Maryland, College Park, kde je profesorem elektrotechniky a počítačového inženýrství na University of Maryland Institute for Advanced Computer Studies (UMIACS). Uzi Vishkin je známý svou prací v oblasti paralelní výpočty. V roce 1996 byl uveden jako Chlapík z Sdružení pro výpočetní techniku, s touto citací: „Jeden z průkopníků výzkumu paralelních algoritmů, klíčové příspěvky Dr. Viškina hrály hlavní roli při formování a formování toho, co paralelní myšlení znamená v základní teorii počítačové vědy.“[1]

Životopis

Uzi Vishkin se narodil v Tel Avivu v Izraeli. Dokončil B.Sc. (1974) a M.Sc. v matematice na Hebrejská univerzita, než si vydělá D.Sc. v informatice na Technion (1981). Poté strávil rok prací v IBM Thomas J. Watson Research Center v Yorktown Heights v New Yorku. V letech 1982 až 1984 působil na katedře počítačové vědy v Newyorská univerzita a zůstal s ním spojen do roku 1988. Od roku 1984 do roku 1997 pracoval na katedře informatiky na univerzitě v Tel Avivu, kde pracoval jako předseda v letech 1987 až 1988. Od roku 1988 pracuje v University of Maryland, College Park.

PRAM na čipu

Pozoruhodná základní abstrakce - kterou každá jednotlivá instrukce dostupná pro provedení v sériovém programu provede okamžitě - zjednodušila sériové výpočty. Důsledkem této abstrakce je podrobná (induktivní) explikace instrukce, která je k dispozici pro další provedení. Základní paralelní abstrakce za konceptem PRAM-on-chip, přezdívaná Iced Concurrent Execution (ICE) v Vishkin (2011), je to, že mnoho instrukcí, které jsou k dispozici pro souběžné provádění, se provádí okamžitě. Důsledkem ICE je postupné (induktivní) vysvětlení (známé také jako lock-step) pokynů, které jsou k dispozici pro další provádění současně. Přesouváme se za sériový počítač von Neumann (dosud úspěšná univerzální platforma pro všeobecné použití), aspirací konceptu PRAM na čipu je, že počítačová věda bude opět schopna rozšířit matematickou indukci pomocí jednoduché jednořádkové výpočetní abstrakce. Chronologický přehled vývoje konceptu PRAM na čipu a jeho hardwaru a prototypování softwaru následovat. V 80. a 90. letech byl Uzi Vishkin spoluautorem několika článků, které pomohly vybudovat teorii paralelních algoritmů v matematickém modelu zvaném paralelní stroj s náhodným přístupem (PRAM), což je zobecnění pro paralelní výpočet standardního sériového výpočetního modelu s náhodným přístupem (RAM). Paralelní stroje potřebné pro implementaci modelu PRAM ještě nebyly v té době postaveny a poměrně málo zpochybnilo schopnost takové stroje vůbec postavit. Uzavírá se v roce 1997[2] že počet tranzistorů na čipu, jak naznačuje Mooreův zákon umožní za deset let vybudovat výkonný paralelní počítač na jediném křemíkovém čipu, vyvinul vizi PRAM-On-Chip, která požadovala vybudování paralelního počítače na jediném čipu, který programátorům umožní vyvinout jejich algoritmy pro model PRAM. Dále vymyslel explicitní vícevláknové (XMT) počítačová architektura, která umožňuje implementaci této teorie PRAM, a vedl jeho výzkumný tým k dokončení v lednu 2007 64procesorového počítače[3] jménem Paraleap,[4] který ukazuje celkovou koncepci. Koncept XMT byl představen v Vishkin et al. (1998), Naishlos a kol. (2003), počítač s procesorem XMT 64 Wen & Vishkin (2008), v Vishkin (2011) a naposledy v Ghanim, Vishkin & Barua (2018), kde se ukázalo, že paralelní programování v uzamčeném kroku (pomocí ICE) může dosáhnout stejného výkonu jako nejrychlejší ručně vyladěný vícevláknový kód v systémech XMT. Takový přístup indukčního lock-stepu stojí na rozdíl od vícevláknových programovacích přístupů jiných mnoha základních systémů, které jsou známé pro náročné programátory. Demonstrace XMT zahrnovala několik hardwarových a softwarových komponent a také výuku algoritmů PRAM za účelem programování XMT Paraleap pomocí jazyka zvaného XMTC. Jelikož je usnadnění paralelního programování jednou z největších výzev, kterým dnes počítačové vědy čelí, demonstrace se také snažila zahrnout výuku základů algoritmů PRAM a programování XMTC pro studenty od středních až po postgraduální studium.

Paralelní algoritmy

V oblasti paralelních algoritmů byl spoluautorem článku Uzi Vishkin Shiloach & Vishkin (1982b) které přispěly rámcem pracovní doby (WT) (někdy nazývaného hloubka práce) pro konceptualizaci a popis paralelních algoritmů. Rámec WT byl přijat jako základní rámec prezentace v knihách o paralelních algoritmech JaJa (1992) a Keller, Kessler & Traeff (2001), stejně jako v poznámkách ke třídě Vishkin (2009). V rámci WT je nejprve popsán paralelní algoritmus z hlediska paralelních kol. Pro každé kolo jsou charakterizovány operace, které mají být provedeny, ale lze potlačit několik problémů. Například nemusí být jasný počet operací v každém kole, nemusí být zmíněny procesory a nemusí být účtovány žádné informace, které mohou pomoci při přiřazení procesorů k úlohám. Zadruhé jsou poskytovány potlačené informace. Zahrnutí potlačené informace je ve skutečnosti vedeno důkazem plánovací věty kvůli Brent (1974). Rámec WT je užitečný, protože i když může značně zjednodušit počáteční popis paralelního algoritmu, vložení podrobností potlačených tímto počátečním popisem není často příliš obtížné. Podobně může být při programování velmi užitečné první přetypování algoritmu v rámci WT XMTC. Vishkin (2011) vysvětluje jednoduché spojení mezi rámcem WT a základní abstrakcí ICE uvedenou výše.

V oblasti paralelních a distribuovaných algoritmů je jedním ze klíčových článků spoluautorem Uzi Vishkin Cole a Vishkin (1986). Tato práce představila efektivní paralelní techniku ​​pro zbarvení grafu. Algoritmus Cole – Vishkin najde a vrchol zbarvení v n-cyklus v Ó(log* n) synchronní komunikační kola. Tento algoritmus je dnes prezentován v mnoha učebnicích, včetně Úvod do algoritmů Cormen a kol.,[5] a tvoří základ mnoha dalších distribuovaných algoritmů pro barvení grafů.[6]

Mezi další příspěvky Uzi Vishkina a různých spoluautorů patří paralelní algoritmy pro seznam pořadí, nejnižší společný předek, klenout se nad stromy, a vzájemně propojené komponenty.

Vybrané publikace

  • Shiloach, Yossi; Vishkin, Uzi (1982a), „An Ó(logn) algoritmus paralelního připojení ", Journal of Algorithms, 3: 57–67, doi:10.1016/0196-6774(82)90008-6.
  • Shiloach, Yossi; Vishkin, Uzi (1982b), „An Ó(n2 logn) paralelní algoritmus maximálního toku ", Journal of Algorithms, 3 (2): 128–146, doi:10.1016 / 0196-6774 (82) 90013-X.
  • Mehlhorn, Kurt; Vishkin, Uzi (1984), „Randomizované a deterministické simulace PRAM paralelními stroji s omezenou granularitou paralelních pamětí“, Acta Informatica, 21 (4): 339–374, doi:10.1007 / BF00264615, S2CID  29789494.
  • Tarjan, Robert; Vishkin, Uzi (1985), „Efektivní paralelní algoritmus biconnectivity“, SIAM Journal on Computing, 14 (4): 862–874, CiteSeerX  10.1.1.465.8898, doi:10.1137/0214061.
  • Vishkin, Uzi (1985), „Optimální paralelní porovnávání vzorů v řetězcích“, Informace a kontrola, 67 (1–3): 91–113, doi:10.1016 / S0019-9958 (85) 80028-0.
  • Cole, Richard; Vishkin, Uzi (1986), „Deterministické házení mincí s aplikacemi pro optimální hodnocení paralelního seznamu“, Informace a kontrola, 70 (1): 32–53, doi:10.1016 / S0019-9958 (86) 80023-7.
  • 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), s. 140–151.
  • Naishlos, Dorit; Nuzman, Joseph; Tseng, Chau-Wen; Vishkin, Uzi (2003), „Směrem k prvnímu vertikálnímu prototypování přístupu s extrémně jemným paralelním programováním“ (PDF), Teorie výpočetních systémů, 36 (5): 551–552, doi:10.1007 / s00224-003-1086-6, S2CID  1929495.
  • Wen, Xingzhi; Vishkin, Uzi (2008), „prototyp procesoru PRAM na čipu založený na FPGA“, Proc. Konference ACM o počítačových hranicích 2008 (Ischia, Itálie) (PDF), str. 55–66, doi:10.1145/1366230.1366240, ISBN  978-1-60558-077-7, S2CID  11557669.
  • Vishkin, Uzi (leden 2011), „Využití jednoduché abstrakce k znovuobjevení výpočetní techniky pro paralelismus“, Komunikace ACM, 54 (1): 75–85, doi:10.1145/1866739.1866757.
  • Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (únor 2018), „Snadné vysoce výkonné paralelní programování na bázi PRAM s ICE“, Transakce IEEE na paralelních a distribuovaných systémech, 29 (2): 377–390, doi:10.1109 / TPDS.2017.2754376, hdl:1903/18521.

Poznámky

  1. ^ ACM: Fellows Award / Uzi Vishkin.
  2. ^ Vishkin, Uzi. Umístit architekturu sady instrukčních sad pro poskytnutí explicitního multithreadingu. US patent 6 463 527. Viz také Vishkin et al. (1998).
  3. ^ University of Maryland, tisková zpráva, 26. června 2007: „Marylandský profesor vytváří stolní superpočítač“.
  4. ^ University of Maryland, A. James Clark School of Engineering, tisková zpráva, 28. listopadu 2007: „Další velký„ skok “ve výpočetní technice získává jméno“.
  5. ^ 1. vydání, oddíl 30.5.
  6. ^ Viz např. Goldberg, Plotkin & Shannon (1988).

Reference

Tento průzkum uvádí 16 příspěvků, jejichž spoluautorem je Vishkin

Cituje 36 článků, jejichž spoluautorem je Vishkin

  • Karp, Richard M.; Ramachandran, Vijaya (1988), „An Survey of Parallel Algorithms for Shared-Memory Machines“, University of California, Berkeley, Department of EECS, Tech. Rep. UCB / CSD-88-408

Tento průzkum uvádí 20 článků, jejichž spoluautorem je Vishkin

Cituje 19 článků, jejichž spoluautorem je Vishkin

externí odkazy