77356

Описание параллельных вычислений при помощи замыканий

Научная статья

Информатика, кибернетика и программирование

Переменная n из множества NMES принимает значение истина только в том случае когда вычислен блок данных с именем являющимся и именем n. Для вычисления в функцию F передаются 1 список аргументов RGS 2 битовый вектор со значениями переменных NMES и 3 вычисленные блоки данных имена которых совпадают с именами переменных из...

Русский

2015-02-02

35 KB

0 чел.

Описание параллельных вычислений при помощи замыканий

М.О. Бахтерев

ИММ УрО РАН, Екатеринбург

Существует необходимость в разработке новых подходов к параллельному программированию, отличных от применяемых в стандартных инструментах разработки параллельных приложений, таких как OpenMP и MPI. Несмотря на многолетний опыт использования и длительное развитие этих инструментов, они не позволяют ни использовать преимущества современных аппаратных платформ, ни эффективно обходить их недостатки. Так, например, в OpenMP до настоящего времени не реализована поддержка систем с архитектурой NUMA, а MPI не позволяет создавать эффективные программы для систем с общей памятью. Кроме того, MPI и OpenMP не позволяют распределять вычисления в неоднородных системах, таких как Roadrunner.

В данной работе рассматривается один из альтернативных методов - программирование параллельных вычислений при помощи замыканий. Эта техника является развитием идей, на которых основывалось ранее предлагавшееся программирование с графом потоков данных (DFG). При попытках разрабатывать в рамках DFG некоторые реальные приложения выяснилось следующее. (1) подход, как и ожидалось, позволяет избавить программиста от значительного объёма работ по созданию подпрограмм для перераспределения данных во время вычисления. (2) как и ожидалось, он позволяет получить такое представление параллельной программы, которое можно эффективно исполнять на разнородном вычислительно оборудовании. (3) но, несмотря на указанные преимущества, программирование в рамках DFG оказалось затруднено необходимостью явно описывать управление потоками данных - в зависимости от условий приостанавливать и возобновлять активность потоков. Это описание часто нужно наделять высокой логической сложностью, особенно в тех случаях, когда граф должен быть перестраиваемым под разное количество вычислительных узлов.

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

Замыканием здесь называется объект: 'F logical_term(NAMES) : ARGS', где F - функция, которая вычисляется после того, как истинным становится logical_term - логическое выражение от множества именованных переменных NAMES. Переменная n из множества NAMES принимает значение истина только в том случае, когда вычислен блок данных с именем, являющимся и именем n. Для вычисления в функцию F передаются (1) список аргументов ARGS, (2) битовый вектор со значениями переменных NAMES и (3) вычисленные блоки данных, имена которых совпадают с именами переменных из NAMES, значения которых на момент начала вычисления F истинны. Результатом вычисления функции F являются множество новых замыканий и/или именованные блоки данных. В такой системе понятий параллельное умножение матрицы на вектор может быть описано программой:

 closure(string_printf("split A : %u %s"; K; expand_string("A.%u"; K)));


closure(string_printf("split b : %u %s"; K; expand_string("b.%u"; K)));



(i = 0; i < K; i = i + 1).do(


 closure("multiply A." + i + " b." + i + " : c." + i)


);



closure(string_printf("join %s : c", expand_string("c.%u & ", K - 1) + "c." + K))

 Видно, что предлагаемый метод очень похож на хорошо известные метод программирования для UNIX-shell (файлы соответствуют именованным блокам данных) и метод развёртки/сокращения (unwind/reduce) в lambda-вычислениях. Представляется, что этот подход с некоторыми техническими расширениями, определяющими способ уничтожения становящихся ненужными блоков данных, может облегчить разработку параллельных программ без ущерба эффективности их исполнения на разнообразном неоднородном оборудовании.

Parallel calculus specification with closures

M.O. Bakhterev

IMM UrB RAS, Yekaterinburg

It is necessary to develop new approaches to parallel programming, which differ from those used in standard parallel application engineering tools such as OpenMP and MPI. In spite of many years experience in use and long-term evolution of these tools, they allow neither to use the advantages of modern hardware nor to avoid its drawbacks. For instance, there is no support for systems with NUMA architecture in OpenMP, and MPI does not provide the creation of effective software for systems with shared memory. Moreover, MPI and OpenMPI do not support distribution of computation in heterogeneous systems, such as Roadrunner.

In this work one alternative method - parallel programming with closures - is considered. This technique is development of ideas, which were the basis for earlier proposed programming with data flow graph (DFG). During attempts to develop some real applications with DFG framework the following was discovered. (1) the approach, as expected, allows to save programmer from considerable volume of works on computation time data distribution subroutines. (2) as expected, it allows to obtain such parallel program representation, that may be efficiently executed on heterogeneous hardware. (3) but despite mentioned advantages, programming with DFG framework turned out to be complicated with need to describe directly the data flow management - the suspending or the resuming of flows depending on conditions. It is often necessary to endow that description with high logic complexity, especially in those cases, where the graph should be reshape-able for various amounts of computational nodes.

During the research of DFG the following was found out. The computations specified by finite data flow graph also may be defined by infinite graph with nodes of much simpler (as compared with finite representation) logical structure. Then it was found out, that the process defined by such infinite graph may be specified with finite way using closure calculus.

The term 'closure' is used here to denote object: 'F logical_term(NAMES) : ARGA', where F is a function, which is calculated after logical expression of the set of the named variables, NAMES - logical_term becomes true. Variable n from NAMES takes true value, if and only if the data block with the exactly same name as the name of n. In order to compute F, the following arguments are passed in this function call. (1) the list of arguments ARGS, (2) bit vector of the values of variables from NAMES and (3) computed blocks of data, whose names equal to the names of variables in NAMES, whose values are true at the moment of calling F. The results of F computation  are new closures and/or new named blocks of data. Using such system of notions one can describe parallel matrix-vector multiplication with program:

closure(string_printf("split A : %u %s"; K; expand_string("A.%u"; K)));
closure(string_printf("split b : %u %s"; K; expand_string("b.%u"; K)));



(i = 0; i < K; i = i + 1).do(


 closure("multiply A." + i + " b." + i + " : c." + i)


);



closure(string_printf("join %s : c", expand_string("c.%u & ", K - 1) + "c." + K))

As it can be seen, that proposing method looks like well known methods: programming in UNIX-Shell with files (where files correspond to named blocks of data) and method of unwind/reduce at lambda-calculus. It may be supposed, that this approach with some technical extensions, determining the way of the deallocation of data blocks becoming useless during computation, may ease parallel programs developing without the loss of the efficiency of these programs execution on different heterogeneous equipment.


 

А также другие работы, которые могут Вас заинтересовать

42928. Краткая характеристика предприятия ОАО «Германий» 111.27 KB
  За эти годы предприятие прошло путь от поставщика продукции на внутренний рынок до экспортера всей номенклатуры выпускаемой продукции в США Израиль Японию страны Европы и Азии. В настоящее время предприятие ГЕРМАНИЙ единственное в России имеющее полный цикл переработки широкую номенклатуру продукции и большие производственные мощности. Команда профессионалов создает продукцию и услуги индивидуально учитывая пожелания потребителей по срокам поставки и качеству продукции ориентируясь на их планы в области бизнеса. до готовой...
42929. Сестринский процесс при стенокардии 173.99 KB
  Предмет изучения: сестринский процесс при стенокардии. Цель исследования: изучение сестринского процесса при стенокардии. Для достижения поставленной цели исследования необходимо изучить: Этиологию и предрасполагающие факторы стенокардии; Клиническую картину и особенности диагностики; Методы исследования и подготовку к ним; Принципы лечения и профилактику стенокардии; Манипуляции выполняемые медицинской сестрой; Особенности сестринского процесса при стенокардии. Нестабильная стенокардия: впервые возникшая стенокардия;...
42930. Расчет двухкаскадного резистивного усилителя на биполярных транзисторах 1.87 MB
  Расчет двухкаскадного резистивного усилителя на биполярных транзисторах пояснительная записка к курсовой работе по электронике Студент гр.130601 Аннотация Данная пояснительная записка написана к курсовой работе по дисциплине Электроника для варианта 03 и содержит в себе результаты расчета резистивного усилителя на биполярных транзисторах. В качестве анализируемого усилителя выступает двухкаскадный усилитель на кремниевых биполярных транзисторах основные параметры которого рассчитываются в одной из...
42931. Анализ организационно-правовых форм предприятий и их особенностей 69.31 KB
  Центральным звеном рыночной экономики в котором принимаются и осуществляются решения об использовании ограниченного количества благ с учётом обстоятельств внешней среды которые не могут быть изменены по воле принимающих решения лиц выбора вариантов решения проблем альтернатив развития или независимых друг от друга вариантов действия направленных на достижение желаемых конечных результатов системы целей являются хозяйствующие субъекты организации предприятия домашние хозяйства...
42933. Проектирование технологического процесса изготовления Шкафа для белья 172.73 KB
  На многопильных форматно-раскроечных станках моделей ЦТМФ осуществляется раскрой плит по картам со сквозными продольными и поперечными пропилами. Для использования однопильного станка достаточно, чтобы на карте раскроя полноформатной плиты или любого раскраиваемого отрезка плиты был хотя бы один сквозной пропил при условии, что осуществление данного пропила возможно по технической характеристике данной модели станка.
42934. Расчет оборудования для вакуум-кристаллизации галургического хлорида калия на БКПРУ-1 1 MB
  Количество испаренной воды в каждой ступени рассчитываем по уравнению теплового баланса где Gnколичество щелока поступающего в nую ступень ВКУ кг ч; Сщел теплоемкость щелока кДж кгС; tн tк перепад температур в nой ступени ВКУ С; rn удельная теплота парообразования на nой ступени ВКУ кДж кг. Сводная таблица материального баланса Состав Приход кг ч Расход кг ч KCl раствор 8455216 3578556 KCl твердый 487666 NCl раствор 7241179 7241179 NCl твердый HO раствор 27354605 24168545 HO испаренная ...
42935. СЕСТРИНСКИЙ ПРОЦЕСС ПРИ АЛЛЕРГОЗАХ 403.51 KB
  Цель исследования: изучение сестринского процесса при аллергозах проведение сестринского обследования выявление настоящих и потенциальных социальных и психоэмоциональных проблем пациента и его семьи определение цели планирование и реализация сестринского процесса. В соответствии с намеченной целью и задачами необходимо использовать следующие методы исследования: научнотеоретический анализ медицинской литературы по данной теме; эмпирический наблюдение дополнительные методы исследования: организационный...
42936. Октановое число, его определение, пути повышения 138.67 KB
  Для лучшего из известных в то время бензинов изооктана 224триметилпентана который детонирует только при высоких степенях сжатия было принято октановое число 100 а для нгептана особенно склонного к детонации октановое число 0. Циклопарафины менее склонны к детонации чем нормальные парафины а ароматические углеводороды отличаются особенно высоким октановым числом. Интенсивность детонации испытуемоготоплива достигается изменением степени сжатия. Октановое число равное 100и ниже обозначает объемную долю изооктана в смеси с...