Cтраница 2
Общий смысл теорем замкнутости заключается в том, что класс алгоритмов, которые в принципе можно переложить на язык тьюринговых программ, замкнут относительно всех употребительных приемов образования новых алгоритмов из алгоритмов уже имеющихся; иначе говоря, коль скоро для исходных алгоритмов возможно задание посредством тьюринговых программ, то это возможно и для результирующих более сложных алгоритмов. В § 10 это было строго доказано для таких важных приемов, как последовательная и параллельная композиция, разветвление и повторное применение алгоритмов. Разумеется, список таких приемов можно было бы продолжить. Однако для всех подобных приемов, которые известны, можно строго доказать аналогичные теоремы. Более того, опыт подсказывает, что в точности так же обстоит дело для всех приемов, которые можно предвидеть в настоящее время. [16]
В этом параграфе неформально представлены элементы и особенности языка. Элементы языка основаны на синхронизованных событиях взаимодействия, недетерминированном выборе между возможными событиями, параллельных композициях, сторожевых операторах, передаче значений и абстракции процессов. Конструкции языка дают возможность описывать хорошо сформированные выражения, определяющие поведение системы или ее частей в терминах событий, возникающих в их точках взаимодействия. [17]
Декомпозиционное дерево T ( G) графа G представляет собой выходящее бинарное дерево ( каждая промежуточная вершина имеет ровно два прямых потомка) с т висячими вершинами. Промежуточным вершинам ( называемым операционными) сопоставлены индексы ( s или р) операций последовательной либо параллельной композиции. Декомпозиционное дерево 74G) графа G определяется итеративно: пусть G G lSG 2 либо G G lPG 2 и деревья Т ( Gi) и Т ( G2) уже построены. Тогда строим новую вершину О, которую делаем непосредственным предшественником корней деревьев Т ( G. [18]
Будем восстанавливать граф G ( 1) по его декомпозиционному дереву Т1, выполняя одновременно некоторые преобразования Gw. Перейдем к декомпозиционному дереву 7 графа G ( i), удаляя из Ti вершины Сг1 и С / 2 и заменяя вершину О вершиной G, где G C sCi если О - операция последовательной композиции, или G CijjC, если О - операция параллельной композиции. [19]
Граф G называется разложимым, если граф G Может быть представлен в виде последовательной либо параллельной композиции двух других графов. В противном случае G называется неразложимым. Gm таковы, что граф G может быть получен из них в результате последовательного выполнения m - 1 операции последовательной и параллельной композиции. [20]
В современной литературе по параллельному программированию интенсивно исследуются программы с независимыми операторами и способы корректного и рационального разбиения их на параллельные ветви. Гораздо меньше внимания уделяется логике перехода от зависимых операторов к независимым. Этому вопросу посвящена работа [ 111, где задача распараллеливания трактуется как задача эквивалентного преобразования последовательной композиции нормальных алгоритмов к параллельной композиции. [21]
Напомним лишь, что граф G, который можно представить в виде последовательной ( G G4sG2) или параллельной ( G G pG2) композиции двух графов GI и G2, называется разложимым ( в противном случае - неразложимым), а графы Gt и G2 - компонентами разложения графа G. Если граф Gt или граф G2 может быть в свою очередь представлен в виде композиции ( параллельной или последовательной) графов G3 и G4, то последние также называются компонентами разложения G. Каждой висячей вершине T ( G) соответствует компонента разложения графа G, а остальным вершинам поставлены в соответствие операции последовательной или параллельной композиции. Висячим вершинам полного декомпозиционного дерева соответствуют неразложимые графы. [22]
Удалим из декомпозиционного дерева Тг вершины Ctl и С / 2, а опорную вершину О заменим вершиной С. Полученное декомпозиционное дерево Tr i имеет п - г висячих вершин, каждая из которых является и-цепью. После выполнения п - 2 шагов получим декомпозиционное дерево 77 1, имеющее две висячие вершины С ( 1), Ст и одну операционную вершину О. Если О - операция параллельной композиции, то, упорядочивая вершины цепей С ( 1) и С2) по невозрастанию их приоритетов, получаем искомую цепь С. В последнем случае цепь С может быть преобразована ( при необходимости) в со-цепь описанным выше способом. [23]
Точно так же имитации работы программы 23 на куске Н может мешать кусок Р или те записи, которые возникли бы в результате его обработки. Конечно, положение сильно упростилось бы, если бы вместо одной одномерной ленты машины Тьюринга в качестве внешней памяти имелись бы две ленты, причем правила функционирования машины допускали бы переписывание с одной ленты на другую. В таком случае можно было бы вычисление ЩР) осуществлять на одной ленте, вычисление 33 ( Я) на другой, и потом можно было бы свести результаты вместе. Это замечание показывает, что для машин другого типа ( с более гибкой и удобной памятью) алгоритм, программирующий параллельную композицию, был бы совсем тривиален. Для машин Тьюринга и для тыо-ринговых программ дело обстоит несколько хуже, но в конечном счете нужный программирующий алгоритм ( и даже в разных вариантах) удается описать. [24]
Правильное течение любого вычислительного процесса обеспечивается тем, что на каждой его стадии в памяти ( машины или вычислителя) сохраняются те данные, которые могут понадобиться на более поздних стадиях. Такие данные не только не могут быть искажены или стерты раньше времени, но и должны размещаться достаточно удобно в памяти, чтобы их можно было отыскать и использовать в нужный момент. В реальных вычислительных машинах это, как известно, достигается засылкой промежуточных результатов в специальные устройства - регистры машины или в ячейки памяти с известными адресами где они хранятся вплоть до того момента, когда они потребуются для дальнейшей обработки. Значительно сложнее обстоит дело для машины Тьюринга; ведь в ее распоряжении имеется лишь одна лента, на которой и можно записывать как исходные. В этом параграфе будут изложены и иллюстрированы некоторые общие соображения и методы, которые позволяют преодолевать трудности, связанные со спецификой внешней памяти машины Тьюринга. В качестве следствия мы получим доказательство теоремы о программировании параллельной композиции, сформулированной и многократно использованной нами в предыдущих параграфах. Однако излагаемые здесь понятия и методы представляют и самостоятельный интерес. Они пригодятся нам и в дальнейшем. [25]