Графы и параллелизм — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Средства создания и проектирования параллельных программ)
(Библиотеки)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 10: Строка 10:
 
===PPBB (Portable Parallel branch-and-bound library)===
 
===PPBB (Portable Parallel branch-and-bound library)===
 
* [http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/SOFTWARE/PPBB/ppbblib.html Официальный сайт]
 
* [http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/SOFTWARE/PPBB/ppbblib.html Официальный сайт]
 +
* Написана на С
 +
* Открытый код
 
The Portable Parallel Branch-and-Bound Library ( PPBB-Library ) presents an easy way to parallelize sequential Branch-and-Bound algorithms for several architectures. A user of the library, who wants to run his sequential algorithm on a parallel system, needs neither knowledge about the hardware architecture nor the parallelization mechanisms.
 
The Portable Parallel Branch-and-Bound Library ( PPBB-Library ) presents an easy way to parallelize sequential Branch-and-Bound algorithms for several architectures. A user of the library, who wants to run his sequential algorithm on a parallel system, needs neither knowledge about the hardware architecture nor the parallelization mechanisms.
 +
 +
===PUBB (Parallelization Utility for Branch and Bound algorithms)===
 +
* Написана на С
 +
 +
===PICO (An Object-Oriented Framework for Parallel Branch and Bound)===
 +
* Написана на С
 +
 +
===Bob++===
 +
* [http://bobpp.prism.uvsq.fr/main.html Официальный сайт]
 +
* Написана на С++
 +
 +
===Acro===
 +
* [https://software.sandia.gov/trac/acro/wiki Wiki]
 +
Acro supports a variety of optimization capabilities, including: <br />
 +
Linear programming <br />
 +
Mixed-integer linear programming <br />
 +
A rigorous nonlinear global optimization solver <br />
 +
Derivative-free local search <br />
 +
Stochastic global optimization methods: multistart local search, evolutionary algorithms <br />
 +
Parallel branch-and-bound <br />
 +
Bound-constrained derivative-based local optimization <br />
  
 
===ParMETIS===
 
===ParMETIS===
Строка 16: Строка 39:
 
PARMETIS - параллельная версия библиотеки [http://glaros.dtc.umn.edu/gkhome/views/metis/ METIS], включающей ряд алгоритмов над графами (parallel graph partitioning).
 
PARMETIS - параллельная версия библиотеки [http://glaros.dtc.umn.edu/gkhome/views/metis/ METIS], включающей ряд алгоритмов над графами (parallel graph partitioning).
 
Реализована с помощью MPI.
 
Реализована с помощью MPI.
 +
 +
===COIN-OR projects===
 +
* http://www.coin-or.org/projects/
 +
* http://www.gams.com/dd/docs/solvers/coin.pdf
  
 
===Математические библиотеки, разработанные в NASA/JPL===
 
===Математические библиотеки, разработанные в NASA/JPL===
<li>DDLIB (Data Distribution Library)
+
* DDLIB (Data Distribution Library)
<li>A Library of Partial Global Operations in Parallel Architectures
+
* A Library of Partial Global Operations in Parallel Architectures
  
 
==Средства создания и проектирования параллельных программ==
 
==Средства создания и проектирования параллельных программ==
Строка 100: Строка 127:
 
Набор программных продуктов для автоматического распараллеливания Fortran/C-программ для SMP-платформ. Есть возможность генерации OpenMP-кода (VAST/toOpenMP).
 
Набор программных продуктов для автоматического распараллеливания Fortran/C-программ для SMP-платформ. Есть возможность генерации OpenMP-кода (VAST/toOpenMP).
 
* Разработчик: компания Pacific-Sierra Research.
 
* Разработчик: компания Pacific-Sierra Research.
 +
 +
== Полезные сылки ==
 +
<li> I. Dorta, C. León, C. Rodríguez and A. Rojasa. MPI and OpenMP implementations of branch-and-bound skeletons.

Текущая версия на 22:22, 17 октября 2010

Библиотеки

ParaLib

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

  • Разработчик: Нижегородский государственный университет им. Н.И Лобачевского, факультет вычислительной математики кибернетики ННГУ, учебно-исследовательская лаборатория «Математические и программные технологии для современных компьютерных систем (Информационные технологии)»

PPBB (Portable Parallel branch-and-bound library)

The Portable Parallel Branch-and-Bound Library ( PPBB-Library ) presents an easy way to parallelize sequential Branch-and-Bound algorithms for several architectures. A user of the library, who wants to run his sequential algorithm on a parallel system, needs neither knowledge about the hardware architecture nor the parallelization mechanisms.

PUBB (Parallelization Utility for Branch and Bound algorithms)

  • Написана на С

PICO (An Object-Oriented Framework for Parallel Branch and Bound)

  • Написана на С

Bob++

Acro

Acro supports a variety of optimization capabilities, including:
Linear programming
Mixed-integer linear programming
A rigorous nonlinear global optimization solver
Derivative-free local search
Stochastic global optimization methods: multistart local search, evolutionary algorithms
Parallel branch-and-bound
Bound-constrained derivative-based local optimization

ParMETIS

PARMETIS - параллельная версия библиотеки METIS, включающей ряд алгоритмов над графами (parallel graph partitioning). Реализована с помощью MPI.

COIN-OR projects

Математические библиотеки, разработанные в NASA/JPL

  • DDLIB (Data Distribution Library)
  • A Library of Partial Global Operations in Parallel Architectures

Средства создания и проектирования параллельных программ

Интегрированные среды прототипирования, разработки и отладки параллельных программ.

CODE

CODE - графическая система создания параллельных программ. Параллельная программа представляется в виде графа, вершинами которого являются последовательные участки, а дуги соответствуют пересылкам данных. Последовательные участки могут быть написаны на любом языке, для пересылок используется PVM или MPI.

  • Разработчик: университет в шт. Техас.

HeNCE (HEterogeneous Network Computing Environment)

Это графическая среда (UNIX/X-Window), разработанная для помощи в разработке параллельных программ, работающих на сети рабочих станций (в модели PVM). Предназначена для вычислителей, желающих эффективно использовать имеющуюся сеть рабочих станций, не вдаваясь в подробности параллельного программирования. HeNCE включает графические средства построения, компиляции, запуска и анализа HeNCE-программ (программист сам не пишет в терминах PVM). Обеспечивает высокий уровень абстракции для спецификации параллелизма. Программа описывается в виде направленного ациклического графа (DAG), в котором вершины соответствуют процедурам, а дуги - зависимостям (зависимости расставляет пользователь). Включает средства графического конфигурирования гетерогенного PVM-кластера для запуска программы.

  • Разработчик: Adam Beguelin, Jack Dongarra, G. A. Geist, Robert Manchek, Keith Moore, Peter Newton, Vaidy Sunderam и др.

GRADE (A Graphical Parallel Programming Environment)

  • [1]
  • Исследовательский проект

GRADE is a graphical environment for parallel programming, based on message passing, initiated in 1994 and developed in the frame of European projects in co-operation with many partners from Hungary and abroad. P-GRADE - профессиональная (коммерческая) версия системы.
Интегрированный набор средств программирования для разработки приложений в модели передачи сообщений на гетерогенных кластерах. Состоит из 6 средств:
GRAPNEL - графический язык параллельного программирования
GPED - графический редактор для построения GRAPNEL-программ
GRP2C - препроцессор для генерации программ на PVM/C
Tape/PVM - средство генерации трасс
DDBG - распределенный отладчик
PROVE - средство визуализации трасс

EDPEPPS

Интегрированная среда для обеспечения быстрого, эффективного и гибкого проектирования переносимых параллельных программ. В EDPEPPS входят 3 основных средства: Графическое средство конфигурирования (configuration tool) для быстрого прототипирования. Средство моделирования (simulation tool), основанное на виртуальной машине исполняющей "скелетные" параллельные программы; генерирует данные о поведении и предполагаемой производительности программы. Средство визуализации (visualisation tool) для изображения интересующих пользователя характеристик, исходя из данных, полученных при моделировании. Представляет собой расширение существующих средств визуализации трасс, таких как Gecko и Paragraph. Схема работы пользователя: Прототирование --> моделирование --> визуализация. Доступен финальный отчет. EDPEPPS: An Environment for the Design and Performance Evaluation of Portable Parallel Software , July 1997. Final Report. M.J. Zemerly.

  • Разработчик: Centre For Parallel Computing at the University of Westminster

DEEP (DEvelopment Environment for Parallel Programming)

  • официальный сайт
  • Коммерческий продукт
  • Модели программирования: общая память (автоматическое распараллеливание циклов или OpenMP), параллелизм по данным (HPF, Data Parallel C), передача сообщений (MPI).

DEEP - интегрированная среда для параллельного программирования. Обеспечивает графический интерфейс, который связывает средства анализа производительности и отладки с исходным кодом программы. Помогает понять структуру и поведение параллельной программы. Подддерживаются языки Fortran (77, 90, 95) и C (а также смешанные программы на Фортране и Си). Платформы: UNIX и Windows NT.

  • Разработчик: компания Pacific-Sierra Research.

Converse

Converse - среда (framework) для поддержки много-языкового параллельного программирования (взаимодействие модулей, написанных на разных языках). Поддерживаются парадигмы обмена сообщениями, объектно-ориентированного программирования, многопоточности. Поддерживаемые платформы: IBM SP, Cray T3E, Origin2000, Exemplar, сети рабочих станций (на базе HP-UX 10, Solaris/SunOS, RS/6000, SGI IRIX, Linux/x86). Доступны двоичные файлы для всех поддерживаемых платформ.

  • Разработчик: Parallel Programming Laboratory (PPL), University of Illinois at Urbana-Champaign.

Средства автоматического распараллеливания

Средства распознавания параллелизма в алгоритмах, средства автоматического и полуавтоматического распаралелливания последовательных программ:

BERT 77

  • Коммерческий продукт
  • Бесплатно доступна LITE-версия

BERT 77 - средство автоматического распараллеливания Fortran-программ, с генерацией параллельного кода в модели обмена сообщениями (PVM или MPI).

  • Разработчик: компания Paralogic.

FORGExplorer

  • Коммерческий продукт

FORGExplorer SMP, FORGExplorer DMP - средства распараллеливания Fortran-программ для SMP и MPP-платформ, работающие на основе базы данных FORGExplorer.

  • Разработчик: компания Applied Parallel Research.

KAP

  • Коммерческий продукт

KAP (Kuck Accelerator Package) - оптимизирующий препроцессор Fortran/C-программ с обнаружением параллелизма. Visual KAP, Visual KAP for OpenMP - визуальные средства автоматического распараллеливания Fortran-программ.

  • Разработчик: компания Kuck & Associates.

VAST/Parallel

  • Коммерческий продукт

Набор программных продуктов для автоматического распараллеливания Fortran/C-программ для SMP-платформ. Есть возможность генерации OpenMP-кода (VAST/toOpenMP).

  • Разработчик: компания Pacific-Sierra Research.

Полезные сылки

  • I. Dorta, C. León, C. Rodríguez and A. Rojasa. MPI and OpenMP implementations of branch-and-bound skeletons.