Лек­ция № 2: Клас­сифи­ка­ция па­ра­л­лель­ных вы­чис­ли­тель­ных си­стем

Май­кл Флинн пред­ло­жил в 1966 го­ду сле­ду­ю­щую клас­сифи­ка­цию вы­чис­ли­тель­ных си­стем, ос­но­ван­ную на ко­ли­че­стве по­то­ков вход­ных дан­ных и ко­ли­че­стве по­то­ков ко­манд, ко­то­рые эти дан­ные об­ра­ба­ты­ва­ют:

Один по­ток ин­ст­рук­цийНе­сколь­ко по­то­ков ин­ст­рук­ций
Один по­ток дан­ныхSISDMISD
Не­сколь­ко по­то­ков дан­ныхSIMDMIMD

Таб­ли­ца 1. Клас­сифи­ка­ция Флин­на

SISD (Single Instruction Single Data): это обыч­ные по­сле­до­ва­тель­ные ком­пью­те­ры. Про­грам­ма при­ни­ма­ет один по­ток дан­ных и вы­пол­ня­ет один по­ток ин­ст­рук­ций по об­ра­бот­ке этих дан­ных. Ины­ми сло­ва­ми, ин­ст­рук­ции вы­пол­ня­ют­ся по­сле­до­ва­тель­но, и каж­дая ин­ст­рук­ция опе­ри­ру­ет ми­ни­маль­ным ко­ли­че­ством дан­ных (на­при­мер, сло­же­ние двух чи­сел).

MISD (Multiple Instruction Single Data): раз­ные по­то­ки ин­ст­рук­ций вы­пол­ня­ют­ся с од­ни­ми и те­ми же дан­ны­ми. Обыч­но та­кие си­сте­мы не при­во­дят к уско­ре­нию вы­чис­ле­ний, так как раз­ные ин­ст­рук­ции опе­ри­ру­ют од­ни­ми и те­ми же дан­ны­ми, в ре­зуль­та­те на вы­хо­де си­сте­мы по­лу­ча­ет­ся один по­ток дан­ных. К та­ким си­сте­мам от­но­сят раз­лич­ные си­сте­мы дуб­ли­ро­ва­ния и за­щи­ты от сбо­ев, ко­гда, на­при­мер, не­сколь­ко про­цес­со­ров дуб­ли­ру­ют вы­чис­ле­ния друг дру­га для на­дёж­но­сти. Ино­гда к этой ка­те­го­рии от­но­сят кон­вейер­ные ар­хи­тек­ту­ры. Сре­ди про­цес­со­ров про­из­вод­ства Intel, кон­вейер при­сут­ству­ет на­чи­ная с про­цес­со­ра Pentium.

SIMD (Single Instruction Multiple Data): один по­ток ин­ст­рук­ций вы­пол­ня­ет вы­чис­ле­ния од­но­вре­мен­но с раз­ны­ми дан­ны­ми. На­при­мер, вы­пол­ня­ет­ся сло­же­ние од­но­вре­мен­но вось­ми пар чи­сел. Та­кие ком­пью­те­ры на­зы­ва­ют­ся век­тор­ны­ми, так как по­доб­ные опе­ра­ции вы­пол­ня­ют­ся ана­ло­гич­но опе­ра­ци­ям с век­то­ра­ми (ко­гда, на­при­мер, сло­же­ние двух век­то­ров озна­ча­ет од­но­вре­мен­ное сло­же­ние всех их ком­по­нен­тов). За­ча­стую век­тор­ные ин­ст­рук­ции при­сут­ству­ют в до­пол­не­ние к обыч­ным «ска­ляр­ным» ин­ст­рук­ци­ям, и на­зы­ва­ют­ся SIMD-рас­ши­ре­ни­ем (или век­тор­ным рас­ши­ре­ни­ем). При­ме­ры по­пу­ляр­ных SIMD-рас­ши­ре­ний: MMX, 3DNow!, SSE и др.

MIMD (Multiple Instruction Multiple Data): раз­ные по­то­ки ин­ст­рук­ций опе­ри­ру­ют раз­лич­ны­ми дан­ны­ми. Это си­сте­мы наи­бо­лее об­ще­го ви­да, по­это­му их про­ще все­го ис­поль­зо­вать для ре­ше­ния раз­лич­ных па­ра­л­лель­ных за­дач.

MIMD-си­сте­мы, в свою оче­редь, при­ня­то раз­де­лять (клас­сифи­ка­ция Джон­со­на) на си­сте­мы с об­щей па­мя­тью (не­сколь­ко вы­чис­ли­те­лей име­ют об­щую па­мять) и си­сте­мы с рас­пре­де­лен­ной па­мя­тью (каж­дый вы­чис­ли­тель име­ет свою па­мять; вы­чис­ли­те­ли мо­гут об­ме­ни­вать­ся дан­ны­ми). Кро­ме то­го, су­ще­ству­ют си­сте­мы с не­од­но­род­ным до­сту­пом к па­мя­ти (NUMA) — в ко­то­рых до­ступ к па­мя­ти дру­гих вы­чис­ли­те­лей су­ще­ству­ет, но он зна­чи­тель­но мед­лен­нее, чем до­ступ к «сво­ей» па­мя­ти.

Си­сте­мы с об­щей па­мя­тью

Си­сте­ма­ми с об­щей па­мя­тью на­зы­ва­ют си­сте­мы, в ко­то­рых не­сколь­ко про­цес­со­ров име­ют об­щую опе­ра­тив­ную па­мять. Ча­ще все­го встре­чаю­щие­ся си­сте­мы это­го ти­па — ком­пью­те­ры с мно­го­ядер­ны­ми про­цес­со­ра­ми (multi-core).

Пре­иму­ще­ства:

  • Не тре­бу­ет­ся об­мен дан­ны­ми: дан­ные, по­ме­щён­ные в па­мять од­ним про­цес­со­ром, ав­то­ма­ти­че­ски ста­но­вят­ся до­ступ­ны­ми дру­гим про­цес­со­рам. Со­от­вет­ствен­но, си­сте­ма не долж­на тра­тить вре­мя на пе­ре­сыл­ку дан­ных.
  • Для та­ких си­стем про­сто пи­сать про­грам­мы: мож­но, на­при­мер, со­здать не­сколь­ко вы­чис­ли­тель­ных по­то­ков, или же снаб­дить про­грам­му спе­ци­аль­ны­ми ди­рек­ти­ва­ми (на­при­мер, тех­но­ло­гия OpenMP), ко­то­рые под­ска­жут ком­пи­ля­то­ру, как рас­па­рал­ле­ли­вать про­грам­му. Кро­ме то­го, воз­мож­но пол­но­стью ав­то­ма­ти­че­ское рас­па­рал­ле­ли­ва­ние про­грам­мы ком­пи­ля­то­ром.
  • Ком­пакт­ность си­стем: мо­жет быть реа­ли­зо­ва­на в ви­де не­сколь­ких про­цес­со­ров на од­ной ма­те­рин­ской пла­те, и/или в ви­де не­сколь­ких ядер внут­ри про­цес­со­ра.

Не­до­стат­ки:

До­пу­стим, у нас есть объ­ект, со­дер­жа­щий чис­ла A и B, и для пра­виль­ной ра­бо­ты объ­ек­та нуж­но, что­бы A + B все­гда бы­ло рав­но ну­лю. Ес­ли пер­вый про­цесс из­ме­нит A, и не успе­ет из­ме­нить B пре­жде, чем вто­рой про­цесс про­чтёт A и B, то вто­рой про­цесс по­лу­чит не­пра­виль­ный объ­ект, в ко­то­ром A + B не рав­но ну­лю. Для ре­ше­ния по­доб­ных про­блем мож­но ис­поль­зо­вать кри­ти­че­ские сек­ции. Ес­ли по­ток ин­ст­рук­ций пер­во­го про­цес­са вхо­дит в кри­ти­че­скую сек­цию с иден­тифи­ка­то­ром N, то по­ток ин­ст­рук­ций дру­го­го про­цес­са не смо­жет вой­ти в кри­ти­че­скую сек­цию с тем же иден­тифи­ка­то­ром, и бу­дет ждать, по­ка пер­вый про­цесс не вый­дет из этой сек­ции.

  • Про­бле­ма сов­мест­но­го до­сту­па к па­мя­ти: нуж­но осто­рож­но ра­бо­тать с те­ми участ­ка­ми па­мя­ти, для ко­то­рых воз­мож­но од­но­вре­мен­ное вы­пол­не­ние за­пи­си од­ним про­цес­со­ром и дру­гой опе­ра­ции (за­пи­си или чте­ния) дру­гим про­цес­со­ром.
  • Про­бле­ма син­хрон­но­сти кэ­шей: для уско­ре­ния до­сту­па к па­мя­ти про­цес­со­ры снаб­жа­ют­ся кэ­ша­ми. Ес­ли один про­цес­сор из­ме­нил дан­ные в опе­ра­тив­ной па­мя­ти, и эти дан­ные про­кэ­ши­ро­ва­ны дру­ги­ми про­цес­со­ра­ми, то их кэ­ши долж­ны ав­то­ма­ти­че­ски об­но­вить­ся. Дан­ная про­бле­ма от­сут­ству­ет в мно­го­ядер­ных про­цес­со­рах, ис­поль­зую­щих об­щий кэш.
  • Про­бле­ма мед­лен­но­го об­ра­ще­ния к опе­ра­тив­ной па­мя­ти и её огра­ни­чен­но­го объ­ё­ма: про­цес­сор ра­бо­та­ет быст­ро, а па­мять — мед­лен­но, по­это­му да­же од­но­му про­цес­со­ру при­хо­дит­ся ждать за­груз­ки дан­ных из опе­ра­тив­ной па­мя­ти. Ес­ли же про­цес­со­ров не­сколь­ко, то им при­хо­дит­ся ждать ещё доль­ше. Ско­рость ра­бо­ты каж­до­го про­цес­со­ра с па­мя­тью ста­но­вит­ся тем мень­ше, чем боль­шее чис­ло про­цес­со­ров име­ет­ся в си­сте­ме. Кро­ме то­го, объ­ём па­мя­ти не мо­жет быть сде­лан сколь угод­но боль­шим, так как для это­го при­дёт­ся уве­ли­чи­вать раз­ряд­ность ши­ны па­мя­ти.
  • Про­бле­ма мас­шта­би­ру­е­мо­сти: очень слож­но сде­лать по­доб­ную си­сте­му с больши́м чис­лом про­цес­со­ров, так как очень силь­но воз­рас­та­ет сто­и­мость и па­да­ет эф­фек­тив­ность ра­бо­ты из-за опи­сан­ных вы­ше про­блем. Прак­ти­че­ски все по­доб­ные си­сте­мы име­ют ≤ 8 про­цес­со­ров.

Си­сте­мы с рас­пре­де­лён­ной па­мя­тью

Си­сте­ма со­дер­жит не­сколь­ко про­цес­со­ров, каж­дый име­ет свою опе­ра­тив­ную па­мять. Для обес­пе­че­ния об­ме­на ин­фор­ма­ци­ей про­цес­со­ры со­еди­не­ны ка­на­ла­ми свя­зи. По ха­рак­те­ру свя­зей та­кие си­сте­мы де­лят­ся на си­сте­мы с уни­вер­саль­ной ком­му­та­ци­ей (каж­дый про­цес­сор мо­жет пе­ре­дать ин­фор­ма­цию лю­бо­му дру­го­му про­цес­со­ру) и си­сте­мы с жёст­кой (фик­си­ро­ван­ной) ком­му­та­ци­ей (каж­дый про­цес­сор мо­жет пе­ре­дать ин­фор­ма­цию толь­ко огра­ни­чен­но­му чис­лу дру­гих про­цес­со­ров).

Си­сте­мы с рас­пре­де­лён­ной па­мя­тью, в ко­то­рых каж­дый вы­чис­ли­тель­ный узел пред­став­ля­ет со­бой пол­но­цен­ный ком­пью­тер со сво­ей ко­пи­ей опе­ра­ци­он­ной си­сте­мы, на­зы­ва­ют кла­стер­ны­ми (или «кла­сте­ра­ми»). Кла­сте­ры обыч­но пред­став­ля­ют со­бой шка­фы с ком­пакт­ны­ми си­стем­ны­ми бло­ка­ми, ко­то­рые со­еди­не­ны друг с дру­гом ка­на­ла­ми свя­зи (по­сред­ством спе­ци­аль­ных ком­му­та­то­ров), пе­ре­даю­щи­ми дан­ные со ско­ро­стью 10 ГБит/сек и бо­лее.

Су­пер­ком­пью­тер Columbia

Ри­су­нок 1. Су­пер­ком­пью­тер Columbia, имею­щий 10240 про­цес­со­ров. По­дроб­нее

Пре­иму­ще­ства:

  • Про­сто­та и де­ше­виз­на по­строе­ния: мож­но взять боль­шое ко­ли­че­ство обыч­ных ком­пью­те­ров, со­еди­нить их ка­на­ла­ми свя­зи (на­при­мер, Ethernet), и по­лу­чить кла­стер.
  • Эф­фек­тив­ное ре­ше­ние за­дач, тре­бую­щих ма­ло­го об­ме­на дан­ны­ми: каж­дый ком­пью­тер бу­дет ра­бо­тать в пол­ную мощ­ность, не ожи­дая, по­ка осво­бо­дит­ся до­ступ к опе­ра­тив­ной па­мя­ти.
  • Воз­мож­ность ре­шать за­да­чи, тре­бую­щие очень боль­ших объ­ё­мов опе­ра­тив­ной па­мя­ти: сум­мар­ный объ­ём па­мя­ти си­сте­мы мож­но сде­лать сколь угод­но боль­шим. Тре­бу­ет­ся лишь, что­бы за­да­ча раз­би­ва­лась на от­но­си­тель­но не­за­ви­си­мые под­за­да­чи.
  • Воз­мож­ность мас­шта­би­ро­ва­ния: мож­но со­еди­нить сколь­ко угод­но вы­чис­ли­тель­ных уз­лов вме­сте, при этом сто­и­мость си­сте­мы бу­дет про­пор­цио­наль­на чис­лу уз­лов. В свя­зи с этим боль­шин­ство са­мых мощ­ных вы­чис­ли­тель­ных си­стем в ми­ре яв­ля­ют­ся кла­стер­ны­ми.

Не­до­стат­ки:

  • Про­бле­ма об­ме­на дан­ны­ми: об­мен дан­ны­ми в та­ких си­сте­мах обыч­но идёт очень мед­лен­но по срав­не­нию со ско­ро­стью вы­чис­ле­ний (и с боль­ши­ми за­держ­ка­ми). По­это­му за­да­чи, тре­бую­щие ин­тен­сив­но­го об­ме­на, не­воз­мож­но ре­шить на та­ких си­сте­мах эф­фек­тив­но.
  • Слож­ное про­грам­ми­ро­ва­ние: про­грам­мист дол­жен про­ду­мать об­мен дан­ны­ми, ко­то­рый бу­дет при­сут­ство­вать в си­сте­ме, дол­жен сам за­про­грам­ми­ро­вать этот об­мен (на­при­мер, с по­мо­щью MPI). При не­пра­виль­ном про­грам­ми­ро­ва­нии ве­ли­ка ве­ро­ят­ность вза­им­ных бло­ки­ро­вок: ко­гда, на­при­мер, два про­цес­со­ра ждут дан­ных друг от дру­га. Про­бле­ма бло­ки­ро­вок есть и в си­сте­мах с об­щей па­мя­тью, но здесь она про­яв­ля­ет се­бя го­раз­до ча­ще. Ав­то­ма­ти­че­ская ор­га­ни­за­ция об­ме­на дан­ны­ми воз­мож­на лишь для не­ко­то­рых ча­ст­ных слу­ча­ев.
  • Боль­шой раз­мер си­стем и боль­шое энер­го­по­треб­ле­ние: кла­стер­ные си­сте­мы за­ни­ма­ют це­лые ком­на­ты (ри­су­нок 1) и да­же зда­ния.

Ги­брид­ные си­сте­мы

Мно­гие со­вре­мен­ные си­сте­мы пред­став­ля­ют со­бой иерар­хию опи­сан­ных вы­ше си­стем. На­при­мер, со­вре­мен­ные про­цес­со­ры яв­ля­ют­ся кон­вейер­ны­ми про­цес­со­ра­ми, и име­ют на­бор век­тор­ных ин­ст­рук­ций (MMX, SSE и т.п.), поз­во­ляю­щих вы­пол­нять од­но­вре­мен­ные вы­чис­ле­ния с раз­ны­ми дан­ны­ми. Кро­ме то­го, про­цес­сор мо­жет иметь два яд­ра, или мо­жет быть не­сколь­ко про­цес­со­ров в ком­пью­те­ре. Та­ким об­ра­зом, на этом уров­не си­сте­ма пред­став­ля­ет со­бой си­сте­му с об­щей па­мя­тью. За­тем мож­но со­еди­нить не­сколь­ко та­ких ком­пью­те­ров в кла­стер, об­ра­зо­вав но­вый уро­вень иерар­хии: си­сте­му с рас­пре­де­лён­ной па­мя­тью.

Что по­чи­тать по те­ме

Flynn's taxonomy – Wikipedia, the free encyclopedia

Non-uniform memory access – Wikipedia, the free encyclopedia

Symmetric multiprocessing – Wikipedia, the free encyclopedia

Cluster computing – Wikipedia, the free encyclopedia

29 отзывов на запись «Лек­ция № 2: Клас­сифи­ка­ция па­ра­л­лель­ных вы­чис­ли­тель­ных си­стем»

Фу бля нет та­кой те­мы ка­то­рой мне но­до фу­у­у­у­у­у­у­у­у­уу
Мне очень жаль.
А для ме­ня есть)
ЗЫ: Оль­га ка­кой-то не­адек­ват т_Т
спа­си­бо очень по­нра­ви­лась лек­ция все чет­ко и яс­но.
Огром­ное Вам спа­си­бо за пре­крас­ные лек­ции. Всё, что я ви­дел на Ва­шем сай­те ис­клю­чи­тель­но ин­те­рес­но. От­дель­но вос­хи­ща­ет Ва­ша тер­пи­мость к «не­цен­зур­щи­кам». PS: link на Ри­су­нок 1. Су­пер­ком­пью­тер Columbia, имею­щий 10240 про­цес­со­ров уста­рел.
Buy Seroquel
lipitor
Buying real online, viagra for women canada .
celebrex online
seroquel
Кек
Ну со­всем кру­то,За­хар ду­рак
buy motilium
amoxil
Augmentin NO Script
inderal 40mg 80mg
It’s a mammoth playground built of mountains, hills, lakes,
That alone wwas an egregious oversight on thheir own part, since
free phone number reverse lookup free reverse phone number
lookup reverse number lookup cell phone free free reverse number lookup
cell phone
wh0cd859862
wh0cd74742 Generic Levitra
wh0cd816070 tadalafil usa
wh0cd264822 online viagra
wh0cd9446 levitra 40 mg
wh0cd414406 Cialis
First of all I want to say fantastic blog! I had a quick question that I’d like to
ask if you don’t mind. I was curious to find out how you center yourself and clear your head before writing.
I have had a hard time clearing my thoughts in getting my ideas out.
I truly do enjoy writing however it just seems like the first 10 to 15
minutes are generally wasted simply just trying to figure out how to begin.
Any ideas or hints? Thank you!
great issues altogether, you just received a emblem new reader.
What could you suggest about your post that you made some days ago?
Any certain?
Hi! I just wanted to ask if you ever have any trouble with hackers? My last blog (wordpress) was hacked and I ended up losing many months of hard
work due to no data backup. Do you have any methods to stop hackers?
Hey very interesting blog!

Оставить отзыв

Жёлтые поля обязательны к заполнению

   

Можете использовать теги <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang=""> <div class=""> <span class=""> <br>