WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 24 |

Временные затраты для выполнения операции умножения матриц разного порядка Размер Время T, с Компиляторы N=1000 N=Borland C++ for Win32 Compiler 5.5 9,60 32,Microsoft 32-bit C/C++ Optimizing Compiler 3,76 13,Intel C++ Compiler 5.0 (включены оптимизи1,50 4,рующие опции) Библиотека PLAPACK (Intel C++ Compiler 2,66 8,5.0) Заключение В работе приводится описание выполненных вычислительных экспериментов, по результатам которых оказалось возможным:

1) проанализировать возможности эффективной организации вычислений с использованием архитектурных особенностей современных процессоров производства корпорации Интел; при проведении экспериментов были разработаны программы для контрольной задачи матричного умножения, которые выполняются быстрее не менее чем на 75% по сравнению с соответствующей процедурой библиотеки PLAPACK 3.0 (для проведения расчетов библиотека PLAPACK использует программную систему MKL разработки корпорации Интел);

2) осуществить выбор системного программного обеспечения для организации параллельных вычислений в многопроцессорных (кластерных) системах; выбранный вариант библиотеки MP-MPICH обеспечивает более чем на 50% лучшую производительность по сравнению с MPICH, являющейся одной из наиболее широко применяемых реализаций стандарта MPI;

3) сравнить эффективность возможных способов разработки параллельных программ для многопроцессорных вычислительных систем с общей памятью; результаты выполненных экспериментов показывают, что использование технологии OpenMP позволяет повысить эффективность параллельных вычислений по сравнению с применением средств передачи сообщений стандарта MPI (эффект ускорения может достигать порядка 40%);

4) оценить возможности технологии комбинированной разработки параллельных программ, при которой для организации взаимодействия между узлами вычислительной системы используются средства MPI, а для обеспечения эффективных вычислений в пределах отдельных многопроцессорных узлов с общей памятью применяется способ распараллеливания на основе OpenMP;

5) изучить масштабируемость (изменение производительности) вычислений при увеличении количества процессоров вычислительной системы для широко применяемой в практических приложениях библиотеки параллельных методов PLAPACK 3.0; эксперименты показали, что увеличению числа процессоров соответствует практически линейный рост производительности вычислений (для задач матричного умножения и решения систем линейных уравнений);

6) проанализировать эффективность вычислений при использовании разных параллельных методов для решения одной и той же задачи; на примере задачи матричного умножения проведено сравнение методов Фокса и Кеннона и ленточного алгоритма; результаты экспериментов показали, что при относительно малых размерах решаемой задачи лучшую эффективность имеет ленточный алгоритм; для матриц более высокого порядка более предпочтительными являются блочные алгоритмы Фокса и Кеннона (различие эффективности может достигать более 200%).

Литература 1. Андреев А.Н., Воеводин Вл.В. Методика измерения основных характеристик программно-аппаратной среды. (www.dvo.ru/bbc/ benchmarks.html) 2. Воеводин В.В. Модели и методы в параллельных процессах. – М.:

Наука, 1986.

3. Воеводин В.В. Математические основы параллельных вычислений. – М.: МГУ, 1991.

4. Гергель В.П., Стронгин Р.Г. Параллельная глобальная оптимизация в многопроцессорных вычислительных системах. // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения». М.: Изд-во МГУ, 2000. С. 87–92.

5. Гергель В.П., Стронгин Р.Г. Параллельные вычисления в задачах глобально-оптимальных решений для многопроцессорных кластерных систем // Труды Международной научной конференции «Математическое моделирование». Самара, 2001. С. 89–92.

6. Гергель В.П., Стронгин Р.Г.. Высокопроизводительный вычислительный кластер Нижегородского университета. // Труды Международной научной конференции» Телематика 2001». СПб.: Изд-во СПбГИТМО, 2001. С. 160–161.

7. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Н.Новгород: Изд-во ННГУ, 2001.

8. Barker, M. (Ed.) Cluster Computing Whitepaper at http://www.dcs.port.ac.uk/~mab/tfcc/WhitePaper/. 2000.

9. Bertsekas, D.P., Tsitsiklis, J.N.. Parallel and Distributed Computation.

Numerical Methods. – Prentice Hall, Englewood Cliffs, New Jersey, 1989.

10. Chandra, R., Menon, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J. Parallel Programming in OpenMP. Morgan Kaufmann Publishers, 2000.

11. Geist, G.A., Beguelin, A., Dongarra, J., Jiang, W., Manchek, B., Sunderam, V. PVM: Parallel Virtual Machine – A User's Guide and Tutorial for Network Parallel Computing. MIT Press, 1994.

12. Group, W., Lusk, E., Skjellum, A. Using MPI. Portable Parallel Programming with the Message-Passing Interface. The MIT Press, 1994.

13. Kumar, V., Grama, A., Gupta, A., Karypis, G. Introducrion to Parallel Computing. – The Benjamin/Cummings Publishing Company, Inc., 1994.

14. Pfister, G. P. In Search of Clusters. Prentice Hall PTR, Upper Saddle River, NJ (2nd edn., 1998).

15. Xu, Z., Hwang, K. Scalable Parallel Computing Technology, Architecture, Programming. McGraw-Hill, Boston, 1998.

16. Zomaya, A.Y. Parallel and Distributed Computing Handbook. / Ed.

A.Y. Zomaya. – McGraw-Hill, 1996.

МНОГОПРОЦЕССОРНАЯ СИСТЕМА СБОРА И ОБРАБОТКИ ДАННЫХ НАУЧНОГО ЭКСПЕРИМЕНТА М.Л. Гольдштейн, А.В. Матвеев Институт математики и механики УрО РАН, Екатеринбург Рассматривается один из возможных вариантов построения многопроцессорной системы сбора и обработки данных (МССОД) с точки зрения получения заданных временных характеристик на примере автоматизированных систем научных исследований (АСНИ) для физического эксперимента в области высокотемпературной электрохимии и медицинского эксперимента для исследования нервно-мышечного аппарата человека. Конкретные временные характеристики АСНИ обусловлены типом объекта и характером эксперимента и лежат во временном диапазоне 10-3 – 10-7 с. В обоих случаях МССОД является составной частью АСНИ с n количеством входов, регистрирующих ряд показателей. В случае электрохимического эксперимента к основным можно отнести ток, потенциал рабочего электрода, количество электричества, температуру, давление и др, в случае медицинского – информацию о форме воздействующих импульсов и реакцию на них.



Подсистема ввода и первичной обработки информации построена как многопроцессорная среда с использованием интеллектуальных плат ввода-вывода (ИПВВ) с цифровыми сигнальными процессорами (DSP) на борту. В настоящее время на одной плате может быть от 1 до 16 DSP, связь между которыми возможна как слабая, так и сильная.

Слабая, когда каждый процессор выполняет свою подпрограмму и обрабатывает данные, хранящиеся в собственной локальной памяти, а обмен данными выполняется через порты ввода-вывода. Сильная, когда каждый процессор обрабатывает данные из некоторого централизованного хранилища, а обмен данными между процессорами выполняется через разделяемую память. Компьютер, содержащий несколько таких плат, обладает достаточно высокой производительностью, однако стоимость подобной системы может оказаться слишком высокой и для многих проектов неприемлемой. Поэтому необходимо разделить обработку данных между быстрыми и дорогими ИПВВ и более медленными и дешевыми многоканальными платами ввода-вывода без процессора (МПВВ). В качестве ИПВВ нами были использованы платы L-783 производства фирмы L-Card, содержащие один процессор ADSP2186. В качестве МПВВ – платы А812PG фирмы ICP DAS.

В общем случае, каждая из рассматриваемых АСНИ реализует четыре основные функции:

1. Фиксация откликов объекта и режимозадающего оборудования Ffx;

2. Формирование управляющих воздействий Fс;

3. Визуализация экспериментальных данных (как прямых, так и расчетных) Fv;

4. Накопление данных Fd.

Обозначим Ffx для функций 2, 3, 4 Ffc, Ffv и Ffd соответственно.

Каждая функция выполняется с определенной частотой. Пусть система имеет n входов: u1, u2, … un (n внешних сигналов). Обозначим хik k-тый отсчет (цифровое значение сигнала) с i-го входа системы. Тогда Fc = Fc (xi1 1, …, x i1 c1; x i2 1, …, x i2 c2; … ; x i 1, …, x i ck), где ij, j = 1, – номер входа системы; сj, j = 1,k – номер отсчета.

Аналогично можно определить:

Fv = Fv (xj1 1, …, x j1 v1; x j2 1, …, x j2 v2; … ; x j 1, …, x j vl), Fd = Fd (xy1 1, …, xy1 d1; x y2 1, …, x y2 d2; … ; x y 1, …, x y dm), Обозначим:

T(Ffc) – критическое время выполнения функции Ffc для данных xi1 1, …, x i1 c1; x i2 1, …, x i2 c2; … ; x i 1, …, x i ck.

T(Fc) – критическое время выполнения функции Fc.

Аналогично определяются T(Ffv), T(Fv), T(Ffd), T(Fd).

Важным показателем системы является время ее реакции на внешние события (термин «время реакции» применим не только ко времени формирования управляющих воздействий, то есть к функции Fc, но также и ко времени визуализации информации и времени сбора данных, например, успеть сохранить блок данных до момента поступления следующего блока). Рассмотрим, каким образом можно сократить его, то есть сумму T(Ffc) + T(Fc), T(Ffv) + T(Fv), T(Ffd) + T(Fd).

Функции Ffc, Ffv и Ffd не имеют принципиального отличия, поэтому далее под функцией Ff будем понимать любую из вышеперечисленных.

Обозначим F’f такие функции Ff, для выполнения которых применяются ИПВВ, F’’f – остальные функции Ff. Аналогично вводятся понятия F’с, F’’c, F’v, F’’v, F’d, F’’d.

В случае малых временных диапазонов (T(Ff) порядка микросекунд и менее) ввод данных в реальном времени однопроцессорной АСНИ затрудняется временными задержками, которые возникают при передаче данных по каналам связи из внешнего мира в вычислительную среду, а также задержками операционной системы (современные операционные системы реального времени имеют задержки порядка нескольких микросекунд). Поэтому во многих случаях единственно возможным решением является перенос вычислительной среды как можно ближе к источникам сигналов, то есть на ИПВВ. Тогда решается вопрос о временных задержках, связанных с передачей данных по шинам расширения, таким как ISA, PCI, VME и т.п. В случае электрохимического и медицинского эксперимента применение ИПВВ было необходимым в силу требования непрерывного сбора и обработки группы данных на частоте до 3 МГц (T(F’f) = 0.3 мкс). Однако, в целях снижения стоимости системы, для фиксации относительно медленно меняющихся величин, таких как температура или давление (T(F’’f) = мс), мы применили МПВВ.

Установка в компьютер нескольких плат с одним DSP позволила организовать одновременный сбор и первичную обработку данных на высокой частоте сразу от нескольких источников. До недавнего времени традиционный подход заключался в формировании последовательных управляющих воздействий центральным процессором и не позволял добиться многоканального сбора и обработки данных на высокой частоте из-за относительно больших временных затрат на передачу данных по каналам связи. В случае с DSP управляющие команды на сбор данных, например, в медицинском эксперименте, осуществляет этот процессор, определяя с какого канала и в какое время получить данные. Таким образом, один DSP может последовательно опросить несколько каналов. Вопрос о применении дополнительных плат с DSP решался с учетом времени аналого-цифрового преобразования, которое выполняется последовательно для каждого канала, а также предельно допустимой частоты сбора данных одним DSP. На плате L-время составило 0.3 мкс. Таким образом, применение нескольких ИПВВ позволяет существенно сократить время T(F’f).





Следующее преимущество ИПВВ – это первичная параллельная обработка полученных данных. Сокращение общего времени обработки T(F’c) + T(F’’c), T(F’v) + T(F’’v), T(F’d) + T(F’’d) происходит как за счет применения параллелизма, так и за счет снижения объема полезных данных, необходимых для централизованной обработки главным процессором. Так, в медицинском эксперименте ИПВВ выделяет из непрерывного потока данных полезный сигнал, и только эти данные передает центральному процессору системы.

В общем случае время реакции системы определяется суммой Т(Ff) + Т(F). Это относится ко всем ее функциям: Fc, Fv и Fd. Однако, организовав двухступенчатый конвейер из периферийного и центрального процессора, можно сократить время реакции до следующей величины: max(Т(F’f), Т(F’’)), что и было сделано в разработанных нами АСНИ. Пока центральный процессор выполняет функции F’’c, F’’v и F’’d, DSP выполняет F’fc, F’fv, F’fd.

Для Fv и Fd данные необходимо передать главному процессору системы, так как только через него возможна связь с устройствами визуализации информации и с устройствами хранения данных. Однако, в случае Fc все данные обрабатываются непосредственно на плате ввода-вывода и здесь же может быть сформировано управляющее воздействие. Тогда Т(F’fc) + Т(F’c) составляет сотни наносекунд, а применение нескольких жестко связанных процессоров на одной плате позволяет существенно сократить время выполнения определенных алгоритмов. В электрохимическом эксперименте, например, одно из управляющих воздействий вырабатывается при прохождении через электролит заданного количества электричества путем непрерывного подсчета, которым занимается DSP. Время реакции системы в этом случае составляет:

Т(F’fc) + Т(F’c) = 0.3 мкс + 0.1 мкс = 0.4 мкс, что полностью удовлетворяет исходным требованиям.

Алгоритмы, выполняемые на подобных платах, как правило, не являются большими, поскольку основное их предназначение – быстрая обработка данных в непосредственной близости от источников сигналов и средств формирования управляющих воздействий, когда время передачи данных в центральный процессор является критичным.

DSP-мультипроцессинг активно применен в разработанных нами АСНИ для электрохимического и медицинского экспериментов, что обеспечило получение заданных временных характеристик и позволило избежать использования такого дорогостоящего программного продукта, как операционная система реального времени.

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ РЕКУРСИВНЫХ СХЕМ РЕДУКЦИИ РАЗМЕРНОСТИ* В.А.Гришагин, В.В.Песков Нижегородский государственный университет им. Н.И.Лобачевского Рассмотрим конечномерную задачу оптимизации:

N f (y) min, y Q R, (1) Q = {y D : g (y) 0, 1 j m}, (2) j N D = {y R : yi [ai,bi ],1 i N}, (3) в которой требуется найти глобальный минимум многоэкстремальной целевой функции f (y) в области Q, задаваемой координатными (3) и функциональными (2) ограничениями на выбор допустимых точек (векторов) y = ( y1, y2,..., yN ).

Многоэкстремальные оптимизационные задачи являются проблемами высокой вычислительной сложности, причем значительное влияние на сложность задачи (1)–(3) оказывает ее размерность N. Так, в случае, когда минимизируемая функция f(y) удовлетворяет в области поиска условию Липшица f (y') - f ( y'') L y'-y'', y', y' ' Q, (4) для задач указанного класса характерен экспоненциальный рост вычислительных затрат при увеличении размерности. В связи с этим естественно использовать ресурсы параллельных вычислительных систем для ускорения процесса анализа и расширения круга исследуемых задач, которые без использования потенциала параллелизма решены быть не могут.

Одним из эффективных подходов к численному решению задач (1)–(3) является подход, основанный на использовании схемы вложен* Работа выполнена при поддержке РФФИ (грант № 01-01-00587) ной рекурсивной оптимизации (многошаговой схемы редукции размерности) [1,2], согласно которой решение исходной многомерной задачи заменяется решением семейства рекурсивно связанных одномерных подзадач, что позволяет применить для решения многомерной задачи известные методы одномерного глобального поиска.

Применение в качестве одномерных алгоритмов оптимизации параллельных характеристических методов глобального поиска [3] позволило построить эффективные параллельные алгоритмы для решения многомерных многоэкстремальных задач. Эти алгоритмы позволяют при использовании 2N процессоров в случае трудновычислимых задач (когда время вычисления функционалов задачи значительно превышает времена обменов данными) добиться эффективности решения, близкой к 95–97%, т.е. экспоненциально ускорить решение задачи за счет, разумеется, экспоненциального увеличения ресурсов (числа процессоров), обеспечивающих процедуру решения.

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

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 24 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.