© Георгиевский Анатолий, 26.10.2005 - 15.09.2008

Представление программ в виде графов

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

Я не теоретик параллельных систем, я не собираюсь выводить формулу абсолютного вычислителя.

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

Процесс можно обозвать «Конвейеризация» Я попробую применять два с половиной языка описания процесса. 1.Схема !Картинка! Цикл обработки данных Операция 1 Операция 2 Операция 3 Операция 4 …. Вариант разбиения задачи: Исходные данные –> Операция 1 –> Выходной Буфер 1 –> передача по сети –> Входной Буфер 2 –> Операция 2 –> Выходной буфер 2 –> передача по сети … Бюджет затрат: Затраченное время = (Время выполнения операции + время передачи по сети)*N*M Где N – количество циклов обработки, M – количество операций на конвейере. Затраченное время = (Время выполнения операции)*N !/Картинка!

Рассмотрим пример, когда необходимо обработать данные объемом 1 Мбайт, на процессоре P = 2ГГц = 2 миллиарда операций/с. На обработку каждого байта тратятся несколько тактов процессора, например, T = 10 операций. На конвейере можно организовать, например, M = 4 операции. По сети G = 1Гбит/с эффективно передаются данные пакетами объемом около S = 1кБайта. При передаче пакета происходит задержка около D = 30 мкс.

Имеет ли смысл разбивать процесс при таком объеме? 1Mбайт/1кБайт C = 1000 циклов

Время, затраченное на обработку задания на ПК =

Время, затраченное на обработку задания на кластере =

Результат очень близкий. Смысла загружать кластер нет! Всегда можно подобрать условия, когда задача будет считаться дольше на кластере, чем на отдельном процессоре. В нашем примере, если взять 3 процессора, на кластере будет считаться дольше. В чем узкое место кластера? В пропускной способности сети. Кроме того, надо иметь в виду накладные расходы при передаче данных и эффективность загрузки процессоров.

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

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

Есть в задаче человеческий фактор, который тоже следует учитывать. Для удовлетворительной эффективности выполнения расчета, надо, чтобы задача считалась в обозримое время. Обычно не важно, считается задача секунду или полсекунды, но весьма существенно, полчаса или пятнадцать минут. Наверное, нет никакого смысла применять кластер, если время расчета обозримо, ожидание результата не томит.

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

Выбор языка моделирования

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

Тут важно правильно поставить задачу, чтобы задача решалась оптимально с точки зрения трудозатрат.

Моя постановка задачи

  1. Максимально допустимое количество процессов – это только параметр программы. В основе программы лежит планировщик заданий, функция которого – автоматическое эффективное распределение ресурсов системы исходя из её параметров. Программа должна иметь возможность исполнения на разнообразных аппаратных платформах без внесения изменений в исходные коды.
  2. Разработка расчетных параллельных программ должна быть проще разработки программ под традиционные однопотоковые архитектуры.

Как бы так на кактус(клустер) влезть?

В школьном курсе дается язык Паскаль, в институтском язык С и Фортран, а для описания параллельных программ алгоритмический язык программирования вообще не годится, нам, надеюсь, хватит русского языка. Вообще, может и не понадобится писать программы – это как задачу поставить, так и решать придется.

Допустим, всё что абстрактно и не описывается физическими соображениями и формулами, может быть автоматизировано. Допустим, нам удалось создать, купить или украсть такое универсальное средство, в которое остается подставить формулы и оно будет с максимальной эффективностью решать нашу задачу.

Такого средства нет? Есть. Оно не видимо, не содержит кода, выполняется между строк готовой программы, весьма параллельно и эффективно.

Представление программ в виде графов

Графы – это картинки – набор стрелок и квадратиков. Квадратики – отдельные функции, описывающие логические или математические преобразования над данными. Квадратики поглощают и производят потоки данных. Данные распространяются по стрелочкам. Любой алгоритм можно представить в виде графа. Дополнительное свойство стрелочек – данные по стрелочкам передаются и воспринимаются по готовности. Уровень абстракции – на усмотрение разработчика.

Граф можно описать в виде таблицы блоков-функций и таблицы связей между блоками. Для этого язык никакой не нужен – это структура данных.

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

Буферизация данных при передаче от одного блока к другому – ещё одна степень свободы для усложения кода. Надо её так же упразднить. Обработка данных происходит порциями, минимальный размер порции определяется пользователем, оптимальный – планировщиком. Планировщик может несколько раз вызвать функцию и накопить буфер до отправки. Таким образом, можно перевалить на планировщика проблему выбора оптимального размера буфера.

Итого планировщик на входе получает идентификатор связи и количество элементов данных в буфере.

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

Получается, что планировщик может быть универсальной программой. Если исключить трудозатраты на создание планировщика, задача решена в общем виде. Остается вписать формулы и логику расчета в соответствующие блоки, заполнить таблицы сообразно структуре графа. На каком языке лучше описывать формулы – дело разработчика. Хорошо бы, чтобы система допускала использование любого привычного.

Потоковая обработка данных

Flow-based programming (FBP). В компьютерной науке потоковое программирование явялется такой же концептуальной идеей, как, скажем, объектно ориентированное программирование (OOP). Описание процесса обработки данных строится в терминах: "черных ящиков" (black box) и связей (net), по которым происходит обмен сообщениями (message passing). В отличие от привычных алгоритмических языков, описывающих последовательность выполнения операций обработки данных, нам небходимо описывать связи. Язык должен быть описательного свойства. Фактически всё что нам нужно - текстовое описание графов.

Как только описание графа представлено в текстовом виде, становится видно основное отличие языка - перестановка поряка описания черных ящиков не влияет на результат.

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

  • асинхронная очередь - это базовый класс, на чем можно построить обмен сообщениями.
  • Mutex - блокироки одновременного доступа на запись и чтение.
  • ассоциативные массивы

Для создания планировщика потребуется подробное изучение разделов:

  • Threads - Нити и ветки
  • Thread Pools - эффективный способ запуска однотипных обработчиков с разными входными параметрами.
  • Сериализация данных, методы кодирования
  • Протоколы передачи данных

( - )