пїњ

’ј–ј “≈–»—“» » “»ѕќ¬џ’ јЋ√ќ–»“ћ»„≈— »’ —“–” “”–*

»Ќ‘ќ–ћј÷»ќЌЌџ≈ “≈’ЌќЋќ√»»
”ƒ  519.683
’ј–ј “≈–»—“» » “»ѕќ¬џ’ јЋ√ќ–»“ћ»„≈— »’ —“–” “”–*
© 2011 г. ¬ад.¬. ¬оеводин
ћосковский госуниверситет им. ћ.¬. Ћомоносова vadim@paraѕel. т
ѕоступила в редакцию 12.07.2010
—уществует предположение, что во многих предметных област€х значительное множество задач построено на основе небольшого числа алгоритмических структур. ѕон€в, какими свойствами обладают эти структуры, можно будет сделать вывод о свойствах и характеристиках самих задач. ¬ данной работе выдел€ютс€ основные этапы процесса отображени€ задачи на некоторую аппаратную платформу и на каждом этапе описываютс€ характеристики, которые определ€ют эффективность отображени€.
 лючевые слова: эффективность программ, типовые алгоритмические структуры, характеристики алгоритмов и программ, процесс отображени€ алгоритма на платформу.
¬ведение
—уществует предположение, основанное как на нашей собственной практике, так и на опыте других, что во многих предметных област€х значительное множество задач построено на основе небольшого числа вычислительных структур [1Ч3]. ¬ этих структурах сосредоточена основна€ вычислительна€ часть задачи. ѕодобные структуры мы будем называть типовыми алгоритмическими структурами. ѕримерами таких структур могут служить умножение матриц, скал€рное произведение, суммирование элементов массива, Ѕѕ‘ или задача N тел. ѕричем кажда€ из этих структур €вл€етс€ типовой дл€ некоторой определенной предметной области (или набора областей), например Ѕѕ‘ €вл€етс€ типовой структурой в области обработки сигналов.
≈сли многие задачи построены на основе типовых структур, значит, пон€в, как устроены типовые структуры, можно пон€ть, как устроены и эти задачи. ј это понимание чрезвычайно важно при построении эффективной реализации задачи на некоторой компьютерной платформе. ѕонимать, как устроена некотора€ структура, -
* —тать€ рекомендована к публикации программным комитетом ћеждународной научной конференции Ђѕараллельные вычислительные технологии 2010ї.
это значит понимать, какими важными свойствами данные структуры обладают, какие характеристики их описывают, на какие параметры надо обращать внимание.
«адача состоит в нахождении подхода к формализации пон€ти€ типовой алгоритмической структуры и после этого - в нахождении подхода к описанию алгоритмической структуры. Ќеобходимо разработать методы исследовани€ и эффективного отображени€ этих структур на конкретные классы параллельных систем и на конкретные архитектуры. ¬ насто€щий момент можно выделить следующие классы архитектур: реконфигурируемые процессоры - FPGA, графические процессоры - GPU, SMP-системы, кластеры и векторные машины. Ёти параллельные платформы наиболее распространены на данный момент, однако нет желани€ ограничиватьс€ только этими архитектурами, а хочетс€ предусмотреть возможность добавлени€ новых платформ, если таковые понадоб€тс€.
«адача отображени€
Ќа рис. 1 приведена обща€ схема отображени€ алгоритма на некоторую платформу. —верху расположены типовые структуры, снизу -конкретные платформы. ’очетс€ отработать путь сверху вниз или, если более конкретно,
 онкретные платформы
–ис. 1. ќбща€ схема отображени€ типовых алгоритмических структур на вычислительные системы
хочетс€ научитьс€ решать, например, такие задачи:
1. ¬ы€вление причин неэффективного отображени€ типовых структур на некоторую платформу.
2. ”прощение процесса отображени€ при добавлении новых алгоритмических структур или новых платформ.
3. ќценка верхней границы степени эффективности отображени€ (в некоторой метрике) определенной структуры на определенную платформу.
4. ќпределение наиболее подход€щей платформы дл€ реализации конкретной структуры.
»зучение процесса отображени€ структур на платформы позволит постепенно определ€ть и фиксировать алгоритм отображени€, поэтому в будущем некоторые шаги будут уже заранее
определены и, возможно, даже будут выполн€тьс€ автоматически.
Ётапы процесса отображени€ типовой структуры на платформу, в общем, совпадают с этапами процесса написани€ обычной программы. ќднако в данной работе важна не сама схема, отражающа€ последовательность шагов в процессе отображени€ алгоритма на архитектуру.  лючевым пон€тием €вл€етс€ эффективность отображени€. ћы хотим исследовать качество данного процесса, дл€ чего нужно знать свойства и характеристики используемых объектов: алгоритмов, программ и компьютерных платформ.  акие особенности архитектуры компьютера вли€ют на эффективность выполнени€ программы? ѕо каким свойствам алгоритма можно судить о возможности его эффективного отображени€ на конкретную компьютерную платформу? Ќа эти вопросы нам поможет ответить исследование харак-
теристик объектов, присутствующих на схеме отображени€.
»сследуемые свойства и характеристики можно разделить на две группы: те, которые мы можем мен€ть, и те, которые мы мен€ть не можем.   первой группе можно отнести такие характеристики, как число процессов или наличие точек синхронизации в программе, а примером из второй может служить характеристика, указывающа€ объем входных данных. ’арактеристики из первой группы определ€ют свободу при выборе отображени€, и изменение их значений приводит к различным вариантам реализации алгоритма. ’арактеристики из второй группы четко фиксированы и определ€ют потенциал эффективного отображени€, который €вл€етс€ показателем того, насколько хорошо в принципе можно отобразить алгоритм на выбранную платформу.
”казанную выше схему в более общем виде можно описать так: изначально задан алгоритм, который затем ложитс€ в основу программы, а написанна€ и готова€ к запуску программа затем исполн€етс€ на аппаратуре. “аким образом, в схеме можно выделить три основные составл€ющие - алгоритм, программа и аппаратура.  ажда€ из этих составл€ющих обладает набором характеристик, которые могут вли€ть на эффективность реализации. ќчень важным €вл€етс€ то, что характеристики алгоритма и аппаратуры принадлежат ко второй группе, то есть не могут быть изменены, в то врем€ как характеристики программы могут мен€тьс€. Ёто означает, что эффективность отображени€ зависит только от того, насколько удачно будет сделан выбор значений характеристик программы, который должен быть произведен с учетом характеристик двух других составл€ющих.
Ќа каждом этапе изначально заложенный в алгоритм Ђпотенциал отображени€ї (насколько хорошо он может быть распараллелен) может только уменьшатьс€, поэтому нужно выделить те характеристики алгоритма, которые вли€ют на эффективность отображени€, а также научитьс€ их оценивать и измен€ть дл€ достижени€ лучших результатов. Ќевозможность повысить эффективность отображени€ при переходе от одного этапа к другому объ€сн€етс€ тем, что с каждым этапом происходит уточне-
ние реализации алгоритма, все больше характеристик и параметров алгоритма четко фиксируетс€, и это накладывает все больше ограничений. ≈сли рассматривать схему отображени€, то на верхнем ее этапе задан только алгоритм и ничего более, поэтому и присутствуют только ограничени€ самого алгоритма. «атем задаетс€ технологи€ программировани€, в рамках которой необходимо писать программу, однако сама программа пока не зафиксирована. ѕосле написани€ программы становитс€ гораздо меньше возможностей вли€ть на способ реализации начального алгоритма, поскольку он фиксируетс€ в коде, и так далее. ѕри этом очень часто нет возможности перейти к следующему этапу без потерь эффективности: например, при написании программы приходитс€ заводить временные переменные и работать с ними, что естественно ведет к таким потер€м. ѕоэтому чрезвычайно важно научитьс€ понимать, какие свойства алгоритма на каждом этапе вли€ют на эффективность его реализации и какие значени€ этих характеристик позвол€ют достигнуть наибольшей эффективности. ќбщей чертой всех этапов €вл€етс€ то, что на каждом из них необходимо учитывать характеристики, которые получены не только на данном этапе, но и на всех предыдущих.
ќписание характеристик различных этапов отображени€
ѕерейдем к рассмотрению этапов отображени€ и выделенных в каждом из них характеристик. ќбща€ схема приведена на рис. 2. —тоит отметить сразу, что данный набор характеристик не €вл€етс€ окончательным и будет в дальнейшем дополн€тьс€.
јнализ информационной структуры алгоритма. –ассмотрим самый верхний уровень, когда известен только алгоритм, а значит, известна и его информационна€ структура [4]. ƒл€ этого будем использовать граф алгоритма, который полностью отражает информационную структуру. √рафом алгоритма называетс€ ориентированный граф, в котором вершины - это множество всех операций алгоритма и из одной вершины идет дуга в другую тогда и только тогда, когда результат операции, вычисл€емой в
–ис. 2. ќсновные характеристики различных этапов отображени€ типовых алгоритмических структур
первой вершине, €вл€етс€ аргументом операции, вычисл€емой во второй вершине. ƒанный граф позвол€ет оценить целое множество полезных свойств, в частности ресурс параллелизма алгоритма, его параллельную и последовательную сложность, длину критического пути €русно-параллельной формы графа, ширину и однородность €русов, общее число операций
[4]; объем входных/выходных данных, отношение числа операций к объему входных/выходных данных и другие. ѕомимо характеристик графа алгоритма, на данном этапе будут учитыватьс€ некоторые другие важные характеристики, такие как тип и разр€дность данных, с которыми работает алгоритм. –азр€дность важна, например, при работе с графическими процессорами, поскольку использование веществен-
ных чисел с двойной точностью вместо одинарной часто существенно снижает скорость выполнени€.
—тоит отметить, что большинство характеристик данного этапа относитс€ к первой группе, то есть нельз€ мен€ть их значени€, поскольку они €вл€ютс€ свойствами исходного алгоритма. ќднако характеристики графа алгоритма определ€ют потенциально возможный параллелизм данного алгоритма, верхнюю границу степени эффективности отображени€. ќни же могут помочь в прин€тии решени€ о том, по какому пути двигатьс€ вниз по схеме отображени€.   примеру, если мощность вычислений, то есть отношение общего числа операций к объему входных данных, слишком мала, то можно сделать вывод, что данный алгоритм вр€д ли полу-
читс€ эффективно реализовать на графических процессорах, поскольку передача данных извне на графический процессор осуществл€етс€ медленно.
ѕосле получени€ и анализа информационной структуры алгоритма желательно определить, на какую архитектуру исходный алгоритм будет отображатьс€, и на основании этой информации выбрать технологию программировани€, поскольку не все технологии могут хорошо подходить дл€ конкретной архитектуры.
Ќаписание и анализ текста программы. ѕосле анализа графа алгоритма и последующего выбора технологии программировани€ наступает этап написани€ программы. «десь накладываютс€ новые ограничени€ на возможности отображени€, поскольку необходимо программировать в рамках выбранной технологии.
—ледующий этап - анализ текста программы. Ќа данном этапе представл€ют интерес такие характеристики, как количество условных переходов и циклов в программе, уровень вложенности циклов; число объ€вленных переменных, и особенно массивов; характеристики параллельности программы - число нитей/процессов, каким образом они порождаютс€ и т.д.; наличие в коде повтор€ющихс€ фрагментов программ (это может быть важно дл€ реконфигурируемых процессоров); количество точек барьерной синхронизации. “акие характеристики, как число циклов и уровень их вложенности, важны потому, что цикл €вл€етс€ одним из основных источников параллелизма, и, следовательно, эти характеристики позвол€ют оценить потенциал распараллеливани€ в рамках написанной программы. ¬ конце данного этапа определ€ютс€ некоторые технические аспекты отображени€, а именно происходит выбор наиболее подход€щего компил€тора и его опций, а также определение подключаемых библиотек, если таковые требуютс€.
 омпил€ци€ и исполнение. ƒалее идет уровень, св€занный с компил€цией программы и ее выполнением. «десь анализируютс€ основные характеристики, касающиес€ работы с пам€тью (локальность данных, необходимый объем пам€ти, общее число обращений в пам€ть), а также коммуникационные характеристики, такие как коммуникационный профиль программы,
объем передаваемых данных, неоднородность пересылок между процессами и т.д.
ќдной из важных и интересных дл€ рассмотрени€ характеристик €вл€етс€ локальность данных. Ћокальность данных определ€ет, насколько близки последующие обращени€ в пам€ть. ¬ зависимости от типа рассматриваемых объектов, выдел€ют локальность команд и локальность использовани€ данных. “акже различают пространственную и временную локальность. ѕространственна€ локальность отражает среднее рассто€ние между несколькими последовательными обращени€ми в пам€ть; временна€ локальность показывает среднее число обращений в пам€ть по одному адресу за врем€ исполнени€ всей программы. јнализ данных характеристик будет проводитьс€ как минимум на двух уровн€х, поскольку €сно, что больша€ часть информации о работе с пам€тью получаетс€ при выполнении программы, но часть информации можно извлечь и на этапе компил€ции (можно оценить долю и профиль использовани€ статических массивов).
Ћокальность использовани€ данных €вл€етс€ частью более общей характеристики - работы с пам€тью. ¬ажным ее свойством, как и свойством некоторых других характеристик, €вл€етс€ то, что они оказывают вли€ние почти на всех этапах отображени€. —оответственно, оценивать их значение и вли€ние необходимо комплексно
и, возможно, с применением отдельного, особого подхода.
ќписание аппаратуры и оценка эффективности. –ассмотрим последний этап - выполнение программы. Ќа этапе компил€ции заканчиваетс€ часть процесса отображени€, св€занна€ со статикой, то есть с исследованием статических свойств алгоритма или программы, и на данном этапе начинаетс€ динамика - изучение программы во врем€ ее исполнени€. «десь дл€ нас важны аппаратные характеристики вычислительных платформ, дл€ которых мы хотим найти эффективное отображение типовой алгоритмической структуры. —юда вход€т такие характеристики, как число процессоров/€дер, тактова€ частота процессора, объем и структура ќ«” и кэш-пам€ти, суперскал€рность, характеристики коммуникационной сети и т.д. ¬ажной особенностью подобных характеристик €вл€ет-
“аблица
ќписание систем, использованных в экспериментах с Ђтриадойї
Ќазвание “ип процессора „астота процессора, GHz —тепень супер-скал€рности €дра „астота FSB, MHz ѕикова€ производительность, GFlops
Clovertown1 Xeon 5310 1.6 4 1066 6.4
Clovertown2 Xeon 5345 2.33 4 1333 9.32
Clovertown3 Xeon 5355 2.66 4 1333 10.64
Woodcrest1 Xeon 5150 2.66 4 1333 10.64
Woodcrest2 Xeon 5160 3.0 4 1333 12
Opteron1 Opteron 280 2.4 2 1000 4.8
Opteron2 Opteron 265 1.8 2 1000 3.6
Harpertown Xeon E5472 3.02 4 1600 12
с€ то, что мы не можем измен€ть их значени€, они только накладывают ограничени€ на потенциал эффективного отображени€, и это приходитс€ учитывать.
— указанными характеристиками тесно св€заны критерии дл€ оценки эффективности отображени€. Ќа их основе мы будем оценивать, насколько эффективно написана программа дл€ данной платформы. Ёто такие критерии, как загрузка процессора, работа с кэш-пам€тью, загрузка сети и т.д. ќни будут сигнализировать о том, что эффективность где-то тер€етс€, а дл€ того чтобы определить, в каком именно месте тер€етс€ эффективность, необходимо Ђподниматьс€ї по схеме отображени€ по уровн€м вверх, чтобы пон€ть, какую характеристику надо изменить дл€ достижени€ большей эффективности. Ќапример, некоторый критерий показывает, что происходит много кэш-промахов. Ёто значит, что в получившейс€ программе плоха€ локальность использовани€ данных. ћожно ли это исправить и как? —начала исследуютс€ характеристики на нижнем уровне, св€занные с локальностью данных, однако причина не здесь, значит, надо подниматьс€ вверх; на этапе компил€ции тоже все нормально; еще на уровень выше, на этапе написани€ программы, видно, что надо было написать циклы в другом пор€дке (или использовать другие структуры данных). ѕосле внесени€ изменений в программе необходимо снова провести анализ характеристик эффективности.
»сследование эффективности реализации типовой структуры Ђтриадаї
–ассмотрим на конкретном примере вли€ние характеристик последнего уровн€ на эффективность реализации. ¬озьмем несколько вариаций типовой алгоритмической структуры Ђтриадаї:
A[i] = B[i]*X+C, (1)
A[i] = B[i]*X[i]+C, (2)
A[i] = B[i]*X+C[i], (3)
A[i] = B[i]*XH+CW. (4)
—оответственно, переменные X и C в одних вариантах €вл€ютс€ скал€рами, в других - массивами. “акже будем рассматривать различные способы адресации массивов в этих вариантах -пр€мую и два варианта косвенной, с использованием дополнительного массива индексов ind. ¬ первом варианте ind1[i] = i, во втором ind2[i] = = (i*K)/N+(i*K)%N, где N - длина массива. ѕервый вариант помогает оценить накладные расходы, привносимые косвенной адресацией, а второй моделирует случай с плохой локальностью данных: константа K подбираетс€ так, чтобы обеспечить максимальный процент кэш-промахов. ѕри этом будем рассматривать самый простой, последовательный вариант решени€ этой задачи, в котором все исполн€етс€ только на одном €дре. ѕри кажущейс€ простоте поставленной задачи ее анализ позвол€ет увидеть много интересного. ƒл€ реализации был выбран €зык — (на ассемблере ничего не писалось), однако выбор €зыка не так важен в данном эксперименте, поскольку эффективность результатов рассматривалась относительно друг друга. ¬ качестве критери€ эффективности использовалось отношение реальной производительности к пиковой.
ƒл€ изучени€ вли€ни€ аппаратных характеристик и получени€ реальных значений эффективности был проведен р€д экспериментов на различных системах. »нформаци€ о системах приведена в таблице.
ќсновные аппаратные характеристики, которые могут оказывать вли€ние на эффективность последовательной реализации, следующие: тактова€ частота €дер, скорость шины FSB (системной шины), частота оперативной пам€ти, объем ќ«” на процессор, размер кэшпам€ти разных уровней, суперскал€рность, наличие векторных операций и т.д.
:{и/1_с11)/(≈––с11/≈––0
–ис. 3. ¬ли€ние характеристики № на эффективность реализации структуры Ђтриадаї
10
о4

64 ћЅ
с I overtown 1
clovertown2 ѕѕ clovertown3 S woodcrestl H woodcrest2 ≈я harpertown
256 ћЅ 512 ћЅ
–азмер массива
–ис. 4. Ёффективность задачи дл€ процессоров линейки Xeon
ѕервые две характеристики сами по себе напр€мую не определ€ют эффективность, однако их отношение €вл€етс€ очень важным параметром, на который, как мы дальше увидим, нужно обращать внимание при рассмотрении эффективности реализаций. » вот почему: эффективность задачи определ€етс€ тем, насколько полно загружен процессор, однако скорость подачи данных по системной шине практически всегда меньше скорости обработки этих данных процессором и, значит, данные просто не будут успевать передаватьс€ по шине процессору. “аким образом, узким местом €вл€етс€ пропускна€ способность системной шины.
¬заимосв€зь частоты процессора и частоты системной шины. Ѕудем рассматривать следующую характеристику: № = (Fcpu*s)/Ffs№, где –сри - частота процессора, 5 - степень суперска-л€рности, Ffs№ - частота системной шины. –ассмотрим вариант (1) типовой структуры Ђтриадаї. ¬ этом варианте идеальным €вл€етс€ значение № =1, поскольку в таком случае системна€ шина перестает быть узким местом (можно и меньше 1, но к лучшим результатам это не приведет, поскольку узким местом станет процессор и эффективность остановитс€ на уровне эффективности самого процессора). ќднако дл€ многих систем
-с1оуег1о\Ђп1 -- \лгоос!сге512
- с1оуеѕо\Ђп2 -ор1егоп1 -
-с10”ег10”Ђ13У
-ор1егоп2
-улгооскгеЅи
№агрег1о\л/п
Х©
Х©
√)
(1)ј[!]= ¬[!]*’ + —
(2)ј[1]=¬[1]*’Ў + —
(3)јЎ=¬Ў*’+—Ў
(4)ј[!]= ¬[!]*’[!] + —Ў
(5) јрпс¬ƒ]] = ¬ѕш)1[Ў*’+—
(6) ј[1пс11[1]] = ¬[1пс11[1]]*’[1пс11[1]] + —
(7) ј[шс11[1]] = ¬[тс11[ѕ]*’ + —[тс!1ѕ]]
(8) ј[1пс11[!]] = ¬[тс11[|]]*’[|ѕ(Ћ[|]] + —[тсѕ[Ў
(9) ј[та2[Ў = ¬[та2[1]]*’ + —
(10) ј[т№2[!]] = ¬[1г^2[Ў*’[ћ2[Ў + —
(11) ј[таг[1]] = врпйрп*х+ сппсвд]
(12) ј[1п<12[1]] = B[ind2[l]]*X[ind2[i]] + —[1пй2[Ў
–ис. 5. ¬ли€ние степени локальности данных на эффективность реализации Ђтриадыї
данное значение далеко от идеального. –ассмотрим св€зь характеристики № с эффективностью реализации нашей задачи. ƒл€ этого сначала посчитаем эффективность дл€ каждой из систем, а затем посмотрим, как соотнос€тс€ значени€ эффективностей дл€ различных систем и их значени€ характеристики №. ƒл€ этого мы считаем отношение эффективностей, деленное на обратное отношение характеристик №. —оответственно, чем ближе полученное значение к 1, тем ближе зависимость рассмотренных двух систем от параметра № друг к другу. Ќазовем этот отношение я, а эффективность будем обозначать ≈г, где г - название системы. ѕриведенные отношени€ показаны на рис. 3: дл€ каждой системы указано значение отношени€ я относительно системы с1оуег1:оЧп1. ћожно видеть, что дл€ всех рассмотренных систем это значение близко к 1, и, значит, дл€ этих систем имеет место практически пр€ма€ зависимость эффективности от значени€ №. Ёто говорит о том, что изменение эффективности на рассматриваемых процессорах определ€етс€ практически исключительно изменением характеристики №, что показывает ее важ-
ную роль.  онечно, в других задачах эта зависимость может прослеживатьс€ не столь €вно, если обращени€ в пам€ть в них происход€т не столь часто.
»з полученного вывода можно вывести интересные следстви€. –ассмотрим эффективность дл€ систем с процессорами из одной линейки -’еоп (рис. 4). ” процессоров с1оуе√;оЧп2 и с1оуе√;оЧп3, а также у обоих процессоров -оо^ сге81 одинакова€ частота системной шины. ѕри этом увеличение тактовой частоты при переходе от одного к другому не приводит к какому-либо реальному ускорению работы программы, однако увеличивает значение пиковой производительности. Ёто, в свою очередь, приводит к обратно пропорциональному уменьшению эффективности программы. “о есть использу€ более мощный процессор мы получаем уменьшение эффективности! ѕохожий эффект можно наблюдать и у процессора №агрейоЧп - у него и тактова€ частота выше, и системна€ шина быстрее, однако отношение № не в его пользу: у №агрейоЧп это значение равно 7.55, а у с1оуег-;о-п2 - 6.99. Ќаилучшее значение характеристики № из рассматриваемых систем у с1оуег-;о-п1 - 6, что и выражаетс€ в наибольшей эф-
фективности. ѕри этом отношение эффективностей с точностью до сотых долей совпадает с отношени€ми их характеристик №.
 эш-промахи. “еперь рассмотрим примеры, когда работа с кэш-пам€тью происходит по разным сценари€м. ƒл€ этого прогоним все 4 варианта задачи со всеми способами адресации и посмотрим изменени€ эффективности. —оответственно, дл€ каждой системы у нас будет 3 группы значений, по 4 в каждой. ƒинамика изменений дл€ всех систем похожа, поэтому мы будем говорить безотносительно к какой-либо конкретной системе.
¬ первой и второй группах результатов кэш-попадание происходило часто, поскольку выборка данных идет последовательна€. ќсновным их отличием €вл€етс€ наличие дополнительного массива индексов т^, что и видно на рис. 5: эффективности тех экспериментов, в которых используетс€ одинаковое число массивов (например, эксперименты (2), (3) и
(5) или (4), (6), и (7)), практически равны. ќднако в третьей группе экспериментов эффективность падает катастрофически, достига€ значений менее 0.2%, - кэш-промахи образуютс€ практически при каждом обращении в пам€ть. ƒанный пример говорит о том, насколько важной характеристикой €вл€етс€ локальность использовани€ данных дл€ оценки эффективности реализации.
«аключение
¬ данной статье рассмотрены некоторые теоретические и практические аспекты процесса выделени€ характеристик типовой алгоритмической структуры и оценки с их помощью эффективности реализации. Ќа простом примере вычислительного €дра Ђтриадаї показано вли€ние этих характеристик. Ётот пример также показывает, что эффективность и простой задачи может зависеть от довольно большого числа различных характеристик и эта зависимость будет становитьс€ все только сложнее с рассмотрением реальных больших задач.
–абота проводилась при поддержке ‘едерального агентства по науке и инноваци€м (государственный контракт ћ 02.740.11.0388), гранта –‘‘» є 10-07-00586-а и гранта ѕрезидента –‘ дл€ молодых ученых ћ -3040.2009.9.
—писок литературы
1. ¬оеводин ¬. ¬. ¬ычислительна€ математика и структура алгоритмов. ћ: »зд-во ћ√”, 2006. 112 с.
2. Asanovic K. et al. The Landscape of Parallel Computing Research: A View from Berkeley. Technical Report є UCB/EECS-2006-183, University of California, Berkeley, Dec. 1S, 2006.
3. Asanovic K. et al. A View of the Parallel Computing Landscape // Communications of the ACM. Nov. 2009. 52, 10. P. 56-67.
4. ¬оеводин ¬.¬., ¬оеводин ¬л.¬. ѕараллельные вычислени€. —ѕб.: Ѕ’¬-ѕетербург, 2002. 608 с.
CHARACTERISTICS OF TYPICAL ALGORITHMIC STRUCTURES
Vad. V. Voevodin
There is an assumption that a large set of tasks in many subject areas is based on a small number of algorithmic structures. Having understood what sort of features these structures have, one can make some conclusions regarding the characteristics and properties of the tasks themselves. In this paper, main stages of the process of task mapping onto a certain hardware platform are identified, and characteristics determining the mapping efficiency are described for each stage.
Keywords: program efficiency, typical algorithmic structures, characteristics of algorithms and programs, mapping of algorithms onto hardware.

пїњ