Графы и параллелизм

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск

Библиотеки

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)

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

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.