r1 - 06 Apr 2005 - 11:52:29 - Artem PervinYou are here: TWiki >  OPENTS Web > Skeletons > SkeletonsIntroduction

Введение в шаблоны параллельного программирования

ШПП это коллекция полезных техник параллельного программирования, которая может быть организована в виде иерархии классов, функций высших порядков или шаблонов. ШПП могут использовать, а могут и не использовать явный параллелизм. Так или иначе ШПП - это некоторая заготовка, пригодная для организации логики параллельной программы. Для того чтобы воспользоваться ШПП пользователю необходимо параметризировать шаблоны/иерархии/функции высшего порядка и снабдить абстрактные конструкции данными об интересующей пользователя задаче.

Важной чертой ШПП является его возможность многократного использования. Организованные в виде абстрактных конструкций ШПП могут быть использованы в ряде самых разных задач, конечно, в том случае если логика решения задачи, удовлетворяет логике организации потоков данных и вычислений в ШПП.

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

Рассмотрим некоторые разработки в области ШПП:

COOPPS - Correct Object-Oriented Pattern-based Programming System

COOPPS призван решить две основные проблемы parallel programming system:

  • Performance: обобщенные средства разработки, как правило, порождают
далеко не самый эффектиный код. Некоторые разработки идут по пути создания некоторый общий набросок и предоставляют его пользователю для вставки application-specific кода и тюнинга приложения. Однако далеко не все такие средства поддерживают последовательный тюнинг кода (incremental code tuning).

  • Generality: такие средства обычно ориентированны на небольшой класс
приложений, если приложение не подходит для той или иной системы разработки, программист не сможет ею воспользоваться. Большинство систем разработки не предоставляют возможностей для определеяемых пользователем расширений.

Для решения этих проблем COOPPS обладает следующими особенностями:

  • параметризируемые каркасы (parameterized frameworks)
  • модель, поддерживающая несколько уровней абстракции
  • инструмент для создания новых ШПП

Пользователю предлагается выбрать удовлетворяющий его задаче шаблон, уточнить его некоторыми параметрами и затем написать application-specfic последовательный код, который будет вызываться средой. Это единственная свясь приложения с COOPPS. Работу по коммуникации, синхронизации, балансировке нагрузки етц, COOPPS берет на себя реализуя их в соотвествии с выбраным шаблоном.

В работе обсуждает задача из вычислительной биологии для которой применяется Wavefront шаблон из библиотеки шаблнов COOPPS. Примеры других доступных шаблонов: pipeline, master-slave, work-queue, mesh, divide-and-conquer.

Шаблоны используются в COOPPS до генерации "каркасного" кода. Так например в Wavefront необходимо уточнить зависимое множество (dependency set) и размер данных (data shape). Это позволяет шаблону покрыть большое множество прикладных задач, при этом не теряя в производительности.

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

  • Patterns Layer:
На этом уровне пользователю доступна только библиотека шаблонов и параметры, передаваемые этим шаблонам. Как только пользователь сделал свой выбор COOPPS создает ОО-каркас приложения, состоящий из абстрактных классов, имплементирующих корректную работу выбранного алгоритма и конкретных подклассов, которые используются для application-specific sequential code.

  • Intermidiate Code Layer:
Этот уровень предоставляет объектно-ориентированный, явно-параллельный язык* программирования. Пользователь может изменять сгенерированную структуру, создавать новый программный код или отлаживать имеющийся

  • Native Code Layer:
На этом уровне код с предыдущего уровня транфсорфируется в исходных объектно-ориентировнный язык (такой как Java или С++). На этом уровне пользователю доступны все библиотеки необходимые для реализации верхних уровней.

*На всех уровнях используется один и тот же язык. Различие составляют окружающие классы.


Diane - DIstributed ANalisys Environment

Diane - это легковестный каркас для создания параллельных научных приложний в модели master/worker. Система предполагает что работа может быть разделена на независимые части.

Diane берет на себе все вопросы коммуникации, сихнронизации и распределенения задач. Выполнение приложения, тем самым полностью контролиуется системой.

Интересной особенностью этой системы является то что она большей частью написана на интерпретируемом языке python. К счастью(?) для пользователей есть возможность создавать свои приложения не только на python. Поддерживаются C++/FORTRAN/Java

Программирование в Diane сводится к работе с тремя очевидными сущностями: Planner, Integrator и Worker. Очевидные они, конечно, только в том смысле что смысл их работы интуитивно понятенчы из названия smile

Вот так выглядит HelloWorld в Diane:

--HelloWorld.h--

#ifndef HELLOWORLD_H
#define HELLOWORLD_H

# include "helloWorld_DXP.h"

namespace helloWorld
{
  class Planner 
  {
  public:
    bool createPlan(JobInitData job_data);
    WorkerInitData workerInit() { return m_init_data; }
    std::vector taskInput() { return m_input_vector; }

  private:
    JobInitData m_job_data;
    WorkerInitData m_init_data;

    std::vector m_input_vector;
  };

  class Integrator
  {
  public:
    bool init(JobInitData input);
    bool addPartialOutput(TaskOutputData output);
    JobResultData getResult();

  private:
    JobResultData m_buf;
  };

  class Worker  
  {
  public:
    bool init(WorkerInitData);
    std::pair performWork(TaskInputData);
    bool done();
  };

  class Protocol
  {
  public:
    typedef TaskInputData TASK_INPUT;
    typedef JobInitData JOB_INIT;
    typedef WorkerInitData WORKER_INIT;
    typedef TaskOutputData TASK_OUTPUT;
  };

}

#endif

---

---HelloWorld.cpp--

# include "helloWorld.h"
# include 

namespace helloWorld
{
  bool Planner::createPlan(JobInitData job_data)
  {
    for(int i=0; i Worker::performWork(TaskInputData)
  {
    TaskOutputData d;
    
    d.answer = "C++: hello from me to you ...";
    std::cout << d.answer << std::endl;

    return std::make_pair(true,d);
  }
  
  bool Worker::done()
  {
    std::cerr << std::endl << "done..." << std::endl;
    
    return true;
    
  }
}

DIANE активно используется в рамках проектов CERN.


DPnDP - Design Patterns and Distributed Process

DPnDP идеологически очень похож на COOPPS: расширяемый набор параметризируемых шаблонов, скрывающих в себе низкоуровневые вопросы синхронизации/коммуникации.

Утверждается что DPnDP поддерживает следующие шаблоны проектирования: task-farm, pipeline, fan-out structure, divide and conquer, and process replication.

Программа на DPnDP представляет из себя граф из модулей из Design Patter`ов, где модули это последовательные программы, взаимодействующие с другими модулями или Design Pattern`ами посредством унифицированных интерфейсов. Design Pattern`ы в свою очередь могут быть вложенным и содержать другие модули/шаблоны.

DPnDP состоит из:

  • User Interface
  • Design Pattern Library (DPL)
  • Code Skeleton Generator (CSG)
  • other supporting libraries

User Interface служит для выбора и уточнения подходящего шаблона.

DPL содержит ШПП написанные в виде C++ классов. Эти шаблоны описывают структуру, поведение и архитектурную информацию. Естественно шаблоны параметризованы. Так например есть шаблон N-stage pipeline описывающий такие шаблоны как 2-stage pipeline, 3-stage pipeline, etc.

Все шаблоны имеют унифицированную форму объявления и определения. Каждый шаблон наследуется от базового, содержащией некоторый общий для всех шаблонов интерфейс. Базовый класс содержит несколько виртуальных функций.

CSG переводит шаблон из промежуточного представления DPL в удобно организованную структуру каталогов с мейкфайлами. Отделение CSG от DPL предоставляет возможность создавать приложения из шаблонов на разных языках, для разных интерфейсов передачи данных и операционных систем без изменения DPL. Так например CSG реализован в виде perl-скрипта.

Еще одной особенностью DPnDP является, т.н., Node Layer инкапсулирующий работу с интерфейсом передачи данных, имеющий снаружи простые для понимания абстракции.


eSkel - The Edinburgh Skeleton Library

eSkel - это структурная (в смысле не ООП) библиотека, предлагающая набор ШПП для опытного C/MPI программиста.

Этим лаконичным описанием все сказано. Программирование в eSkel достаточно близко к низкоуровнемому MPI-программированию.

eSkel поддерживает следующие шаблоны: pipeline, deal, butterfly, fram, haloswap. В текущей версии доступны только pipeline и deal.

Напоследок кусок кода из примеров программ на eSkel:

// Main procedure, defining the Pipeline parameters and calling the Pipeline
int main (int argc, char *argv[])
{
  int i, j, p, next;
  spread_t spreads[STAGES+1];
  MPI_Datatype types[STAGES+1];
  Imode_t imodes[STAGES];
  int outmul;
  int mystagenum;

  int mymult;
  int *inputs, *results;
  double secs;
  
  eSkel_molecule_t *(*stages[STAGES])(eSkel_molecule_t *); 

  MPI_Init(&argc, &argv);
  SkelLibInit();

  // ...

  // Call to the Pipeline function
  Pipeline (STAGES,  imodes, stages, mystagenum, BUF, spreads, types, 
      (void *) inputs, INPUTSZ, INPUTNB, (void *) results, INPUTSZ, &outmul,
      INPUTNB*INPUTSZ, mycomm());

  // ...

  // End MPI
  MPI_Finalize();
  return 0;
}


muskel - muskel

muskel - это Java библиотека. muskel предоставляет несколько ШПП: task farm(master/worker) и pipeline. Предполагается что небольшого количества ШПП достаточно для того чтобы реализовать большое количество практических параллельных приложений.

Для того чтобы создать параллельное приложение с muskel надо:

  1. описать последовательный код в шаблоне Compute.
  2. структурировать программу используя шаблогы Farm и/или Pipeline
  3. объявить менеджер, указав количество процессорных элементов, необходимых для вычисления и...
  4. ... велеть менеджеру посчитататься.

Все это мы где то уже видели: объект compute похож на тфункцию. Farm/Pipeline похожи на то к чему мы идем - объекты реализующие обозначенную вычислительную модель, расщепляя исходную задачу на множество Compute`ов (т-функций). Ну а менеджер это понятно -- планировщик.


SKIL - Skeleton Imperative Language.

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

Расширения:

  • Type variables для поддержки полиморфизма.
Это шаблоны, которые могут быть инстанцированы любым типом кроме void и функциональных типов (functional types).

пример:

$t x; /* variable declaration */

$y id ($y x)    /* function declaration */
{ return (x); } 

Кроме того, type variables могут быть использованы при объявлении структур, объединений или pardata (распределенных) типов.

привер:

typedef struct _list <$elem_t> { /* definition of polymorphic list */
 $elem_t elem;
 struct _list <$elem_t> *next;
};

pardata matrix <$item_t>;       /* 'pardata' declaration */

  • Модификатор типа "pardata"

Это модификатор предназначен для обозначения распределенных ("параллельных") типов данных. pardata может иметь type variable в качестве аргумета. pardata данные не могут быть вложеными.

  • Поддержка функций высших порядков

Skil поддерживает функции высших порядков, аргументами которых или результом работы может быть функция. Тем не менее на функциональные выражения существует ряд ограничений. Так например оно не может быть аргументом следующих операторов: assignment (=), conditional (?:), sequence (,), cast, sizeof;

  • Преобразование операторов в функциях

В Skil введена аналогичная Haskell поддержка инфиксных операторов, указываемых при вызовах функций. Список операторов для которых это применимо: ||, &&, |, ^, &, =, , <, >, <=, >=, <<, >>, +, -, *, /, %, ~ и !.

Выглядит это как-то вот так:

   a = array_create (1, totalsize, def_blsize, def_lowerbd,
                     rand_traj (x0, y0, h, n/netSize)) ;

   res  = array_fold (ident, (+), a, pck_f, upck_f, dup_f) ;
   res /= n                                                ;

   array_destroy (a, destroy_f) ;
Результатом вызова array_fold здесь является сумма массива a.

-- Artem Pervin - 06 Apr 2005

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r1 | More topic actions
 
Powered by TWiki

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback