Математика – эликсир мудрости. Закон Амдала. Программирование три в одном

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

В законе Амдала, вроде, все правильно, но что-то не так и не то. Подобные сомнения возникли почти сразу после знакомства с ним. Но, правда, кто я такой, чтобы давать оценку? Да и интересовали меня на тот момент другие проблемы, к которым данный закон имел, как мне представлялось, косвенное отношение.

Однако, «давно не было такого и вот опять» – свежая статья на Хабре про закон Амдала, да еще и с настоятельной рекомендацией его изучать[1]. Пришло, видимо, время мне на эту тему высказаться. Хотя бы в пику его «обязательности чтения», т.к. для тех, кто «проектирует параллельные системы», подобные советы представляются не только излишними, а даже вредными.  

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

Так давайте попробуем понять кто прав, а кто нет.  А поможет нам математика, которую можно не понимать, можно даже не любить, но не уважать нельзя.

Параллельные задачи

Так что же представляет собой закон Амдала с моей точки зрения?

Процитируем источник. «По версии Амдала, скажем так, около 40% реальных вычислительных задач приходится на последовательную часть — обслуживание данных, управление памятью. По его оценке, если вынести эти доп. расходы на отдельный процессор, реальный выигрыш составит 5-7x — но никак не линейное ускорение с числом процессоров» [1]. 

Но насколько подобная «версия» верна и верна ли вообще?

Уточним для начала класс «реальных вычислительных задач». Нет сомнений, что речь идет о программах, представленных текстовой формой или просто — листингами. А они всего лишь одна из форм описания алгоритмов. Да и ключевое слово здесь должно быть – не задача, а алгоритм. И термин «алгоритм» вне понятия «модель алгоритма» это тоже ни о чем. Таким образом, рассматривая вопросы распараллеливание, мы должны рассуждать об алгоритмах в рамках той или иной вычислительной модели.

Рассуждая о «пределах», мы  должны использовать формально строгие понятия. В нашем случае это «вычислительная модель» и «алгоритм». А они были формализованы достаточно давно. И хотя моделей алгоритмов известно большое число, можно сосредоточиться на одной, т.к. путем эквивалентных преобразований они приводятся к небольшому числу базовых алгоритмических моделей. Разработка подобных механизмов входит в число обязанностей теорий, вводящих в оборот модели, которые еще часто абстрактными машинами (АМ). К наиболее известным из них относятся машина Тьюринга (МТ) и машина Поста (МП).

Но далее  мы ограничимся самой известной формой подобных «машин» – блок-схемами (БС). А это все равно, что машина Поста. Только в отличие от МП о БС знают все – от школьников до состоявшихся программистов. Но кроме текстовой формы БС существуют и другие ее формы. Среди них графическая форма, т.е. граф блок-схемы. Но почему-то программисты их не очень любят. Но для нас важно, что эти формы эквивалентны и перетекают одна в другую. И тут поневоле вспоминается структурное программирование и блок-схемы из книг Э.Дейкстры и Н.Вирта.

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

Формулируя свой закон Амдал, имел в виду, видимо, именно модель БС. Хотя бы в силу того, что это была и есть самая распространенная алгоритмическая модель. На аппаратном уровне ей соответствует фон-неймановская архитектура процессоров. Заметим, что число подобных процессоров/ядер никоим образом не влияет на саму модель алгоритма, которую, скорее всего, забыл упомянуть не только автор закона, но и автор обсуждаемой статьи.

Справедливости ради нужно упомянуть и тех, кто не забыл об алгоритмах и их графических вариантах. Например, в [2] в контексте рассмотрения закона Амдала упоминается одна из графических форм —  графы информационных зависимостей. Таким образом, предлагая оценку параллелизма задач по алгоритмам, мы не являемся здесь первопроходцами. И это хорошо, т.к. есть база, от которой можно оттолкнуться, и есть, если что, с чем сравнивать.

Модель параллельного алгоритма

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

Собственно эта сложность и породила «простое решение» – многопоточное программирование. Но простым его можно считать только с точки зрения аппаратной реализации.  Самим же программистам простая жизнь не грозит. В результате мы имеем то, что имеем — сложные, запутанные и ненадежные программные решения, порожденные топорной реализацией/имитацией параллелизма.

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

Для начала представим программу, как некий «черный ящик» (ЧЯ), имеющий множество входных и выходных каналов (см. [4]). А теперь представьте, что все входные каналы и в общем случае какое-то подмножество выходных каналов могут исполняться параллельно. Это, если вы согласны с таким представлением, распараллеливание на структурном уровне. Какие-то проценты можно подсчитать уже сейчас, но — рано. Хотя закон Амдала оперирует процентами, пожалуй, именно на таком уровне.

Точную оценку степени параллелизма программы можно получить, перейдя от структурного уровня на модель поведения ЧЯ, т.е. уровень алгоритма. По поводу алгоритмической модели ЧЯ в форме блок-схем   мы уже высказались. Нужна другая модель. И она есть. Это модель конечного автомата. Подробно с моделью автоматного программирования можно познакомиться в [5]. И это желательно сделать, чтобы лучше был понятен смысл дальнейших рассуждений.

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

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

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

Далее за параллелизмом элементов отдельного автомата следует параллелизм множества автоматов – сетевая автоматная модель. Весь описанный только что параллелизм отдельной программы в деталях описан в [5].

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

Программирование «три в одном»

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

Но вернемся к автоматам и покажем, что технология автоматного программирования (АП) не исключает использования других моделей внутри технологии АП. Как реализуется такой «многомодельный подход» продемонстрируем на примере задачи о светофорах, приведенной в [6].

Алгоритм светофора для пешеходов в форме «три в одном» приведен на рис 1. Алгоритмы светофоров для автомобилей будут почти такими же по виду. Эта модель может работать, используя модель управления в автоматной форме, на базе таймера или в режиме потоков.

В соответствии с графом, переход из состояния «xx» в «ss» выполняется поле успешной инициализации модели. Предикаты x11, x13 и x14 определяют заданный режим работы – 1) автоматное управление, 2) управление от таймера или 3) реализацию на потоках. В результате выполняется переход соответственно в состояния «st», «tt» или «t2». В данных состояниях ожидается нажатия кнопки «Start test» (см. рис. 2). Это зависит от значения предиката x5.

Для управления тестом создан диалог, вид которого приведен на рис. 2. Он имеет поле, в котором можно задать режим управления. Справа от него индицируется текущий режим работы. Поле «NumberOfFrames» задает число кадров, где кадр – 55 тактов работы светофоров (см. диаграмму работы светофоров на рис. 2 в [6]). Блоки индикаторов отражают текущее состояние светофоров и текущий номер такта диаграммы. Поле «Code» соответствует строке «Код диаграммы». Поле «Count» – номер текущего такта диаграммы, поле «frame time» — время исполнения текущего кадра. Переключатель «View Counters» запускает вывод текущих значений счетчиков в рамках среды разработки, а кнопка «Open the Crosswalk dialog» демонстрирует пример создания диалога для отдельного процесса.

Блок контролов, помеченный VCPa, содержит элементы управления автоматным ядром. Здесь «Stop All Tasks» останавливает работу всех автоматных процессов. После нажатия кнопка меняет название на «Start All Tasks» и инициирует продолжение работы процессов. Поле «Delta Time» задает значение дискретного такта автоматного ядра. Переключатель «step-by-step» переводит ядро в пошаговый режим работы, где однократное нажатие кнопки «step-by-step» реализует один такт работы ядра.

Кнопка «Restart VCPa» запускает процедуры инициализации всех автоматных процессов, которые для этих целей содержат метод ResetAction().Для перезапуска теста нужно нажать сначала кнопку сброса, а затем кнопку «Start Test», задав перед этим параметры работы – число кадров, дискретное время такта и т.д. и т.п.

Режимы работы теста

Приведенный диалог управления тестом позволяет проводить тестирование без перезагрузки теста. Для этого необходимо: 1) нажать кнопку «Restart…», 2) установить нужные параметры работы, 3) нажать кнопку «Start Test».

В режиме «Автоматное управление» автомат попадает в состояние «s1», где в цикле, пока не будет сброшен флаг «demoFSM», будет исполняться действие y14, которое реализует диаграмму работы светофора. Варианты действия y14 для соответствующих автоматных классов светофоров показаны на листинге 1.

void FCrossEasy::y14() {    nCounter = pVarCounter->GetDataSrc();    if (nCounter == 0) { y2(); y3(); y8(); }    else if (nCounter == 20) { y1(); y4(); }    else if (nCounter == 30) { y2(); y3(); }    nCounter++;    int nMax = pVarMaxCntr->GetDataSrc();    if (nCounter == nMax) { nCounter = 0; }    pVarCounter->SetDataSrc(nullptr, nCounter);}…void FLightEasy::y14() {    nCounter = pVarCounter->GetDataSrc();    if (nCounter == 0) { y2(); y3(); y5(); y16(); }    else if (nCounter == 30) { y4(); }    else if (nCounter == 35) { y1(); y3(); y6(); y15(); }    else if (nCounter == 45) { y5(); }    else if (nCounter == 46) { y6(); }    else if (nCounter == 47) { y5(); }    else if (nCounter == 48) { y6(); }    else if (nCounter == 49) { y5(); }    else if (nCounter == 50) { y4(); }    nCounter++;    if (nCounter == pVarMaxCntr->GetDataSrc()) { nCounter=0; }    pVarCounter->SetDataSrc(nullptr, nCounter);}

В режимe «Таймерное управление» автомат попадает в состояние «t1».По дороге запускаются последовательно действия y13 и y11. Код этих действий приведен на листинге 2. В результате их работы автомат переводится в режим останова (хотя это и не обязательно) и далее работает только код обработчика сообщений от таймера – timerEvent Его код вместе с действиями y11 и  y13 приведен на листинге 2.

void FCrosswalk::y13() {    int n = 0;    if (pMainWindow->pVarSet->bIfSynchronousOperation) {        n = pVarSleep->GetDataSrc();        n = pMainWindow->pVarSet->dDeltaTime;    }    nIdTimer = startTimer(n-pMainWindow->nDeltaDelta);}…void FCrosswalk::y11() { FStop(); nStateTimer = 11; }…void FCrossEasy::timerEvent(QTimerEvent* t) {    if (nIdTimer != t->timerId())        return;    switch(nStateTimer) {    case 11:        if (x5()) { y14(); nStateTimer=1; }        break;    case 1:        if (x4()) { y14(); }        else if (!x4()) { nStateTimer = 11; }        break;    }}

В режимe «Потоковое управление» автомат попадает в состояние «t3».По дороге действие y17  создает класс потока. Код данного действия и код потока приведен на листинге 3.

void FCrosswalk::y17() {    QThread *pThread = thread();    // ссылка на текущий поток    pThCrosswalk    = new ThCrosswalk(this, pMainWindow);}ThCrosswalk::ThCrosswalk(FCrosswalk *p, QObject *parent) :    QThread(){    pFCrosswalk = p;    bIfRun = true;      // установить признак запуска/завершения потока    start(QThread::IdlePriority);            // запустить поток    nState = 11;}ThCrosswalk::~ThCrosswalk() {    if (bIfRun) { bIfRun = false; quit(); wait(); }    bIfRun = false; quit(); wait();}void ThCrosswalk::run(){    bIfStop = false;       // сбросить признак останова потока    int nSleep = 0;    if (pMainWindow->pVarSet->bIfSynchronousOperation) {        nSleep = pMainWindow->pVarSet->dDeltaTime;    }    while(bIfRun)  {        if (bIfExecuteStep) {            bIfExecuteStep = 0;            if (pFCrosswalk->x5()) {                while (pFCrosswalk->x4()) {                    if (bIfExecuteStep) {                        bIfExecuteStep = 0;                        if (pFCrosswalk->nCounter == 0) {                            pFCrosswalk->y2();                            pFCrosswalk->y3();                            pFCrosswalk->y8();                        }                        if (pFCrosswalk->nCounter == 20) {                            pFCrosswalk->y1();                            pFCrosswalk->y4();                        }                        if (pFCrosswalk->nCounter == 30) {                            pFCrosswalk->y2(); pFCrosswalk->y3();                        }                        msleep(nSleep-pMainWindow->nDeltaDelta);                        pFCrosswalk->nCounter++;                        if (pFCrosswalk->nCounter == pFCrosswalk->pVarMaxCntr->GetDataSrc()) {                            pFCrosswalk->nCounter=0;                        }                    }                }            }        }    }    bIfStop = true;        // установить признак останова потока}

Не приведенные в листингах коды методов принадлежат родительским классам. Полный код проекта, включая код автоматного ядра, размещен на GitHab и доступен по ссылке (https://github.com/lvs628/VCPa-mini.git). Код проекта проверен в среде Qt Creator версии 5.14.

Результаты работы теста во всех трех режимах представлены на рис. 3. Обратите внимание на время работы, где автоматная модель управления реализует наиболее точное время работы.

Заключение

Рассмотренный пример, судя по графу автомата, не отличается высокой степенью параллелизма. Это не опровергает и не подтверждает «версию» Амдала. Но, с другой стороны, каждый светофор – это параллельный процесс и в результате имеем три полностью параллельных процесса. Как все это оценить в «процентах», чтобы применить формулу Амдала, для меня загадка. Поскольку, если оценить параллелизм одного процесса светофора, то он фактически нулевой. Но, с другой стороны,  мы имеем три параллельных процесса. Если их «разбросать» по ядрам, то, вероятно, будет трехкратное ускорение.

Рассмотренный в статье пример отражает очевидный факт, что параллелизм, прежде всего, совсем не про скорость работы программы, а про решение проблемы сложности программирования. Есть ли закон, который мог бы отразить подобное качество? У меня большие сомнения.

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

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

Литература

1.       Закон Амдала – математика против маркетинга многоядерности. https://habr.com/ru/articles/1054424/

2.     Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002. – 400 с.

3.     Дэвид Дж. Ивенс. Системы параллельной обработки. М.:Мир, 1985 – 413 с.

4.     Минский М. Вычисления и автоматы. М.: Мир, 1971. – 364 с.

5.       Автоматное программирование: определение, модель, реализация. https://habr.com/ru/articles/682422/

6.       Бониана: приложение к браслету. https://habr.com/ru/articles/1032508/