Image Processing

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

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), ко­то­рые под­ска­жут ком­пи­ля­то­ру, как рас­па­рал­ле­ли­вать про­грам­му. Кро­ме то­го, воз­мож­но пол­но­стью ав­то­ма­ти­че­ское рас­па­рал­ле­ли­ва­ние про­грам­мы ком­пи­ля­то­ром.
• Ком­пакт­ность си­стем: мо­жет быть реа­ли­зо­ва­на в ви­де не­сколь­ких про­цес­со­ров на од­ной ма­те­рин­ской пла­те, и/или в ви­де не­сколь­ких ядер внут­ри про­цес­со­ра.

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

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

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

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

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

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

• Про­сто­та и де­ше­виз­на по­строе­ния: мож­но взять боль­шое ко­ли­че­ство обыч­ных ком­пью­те­ров, со­еди­нить их ка­на­ла­ми свя­зи (на­при­мер, 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