Организация обслуживания вычислительных задач

В зависимости от вида вычислительной системы (одно- или многомашинной), в которой организуется и планируется процесс обработки данных, возможны различные методы организации и обслуживания очередей заданий. При этом преследуется цель получения как можно лучших значений таких показателей, как производительность, загруженность ресурсов, малое время простоя, высокая пропускная способность, разумное время ожидания в очереди заданий (задание не должно ожидать „вечно“).

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

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

На рис. 3.11 изображена схема организации вычислительной многомашинной системы, где упорядочение очереди из потока заданий осуществляется диспетчером Д1, а ее обслуживание ЭВМ осуществляется через диспетчера Д2.

 

 

Рис. 3.11 Схема организации обслуживания заданий в многомашинной вычислительной системе

 

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

Система (в нашем случае вычислительная система) изменяет свои состояния под действием потока заявок (заданий) - поступающие заявки (задания) увеличивают очередь. Число заданий в очереди плюс число заданий, которые обрабатываются ЭВМ (т.е. число заданий в системе), - это характеристика состояния системы. Очередь уменьшается, как только одна из ЭВМ заканчивает обработку (обслуживание) задания. Тотчас же на эту ЭВМ из очереди поступает стоящее впереди (или по какому-либо другому приоритету) задание, и очередь уменьшается. Таким образом, число заданий в системе (в очереди плюс на обслуживание) растет благодаря потоку заданий, а уменьшается - благодаря окончанию обслуживания с помощью ЭВМ. Устройства обработки заявок в теории СМО называют каналами обслуживания. В этой теории поток заданий (заявок на обслуживание) характеризуется интенсивностью l - средним количеством заявок, поступающих в единицу времени (скажем, в час). Среднее время обслуживания (обработки) одного задания t _обопределяет, так называемую, интенсивность потока обслуживания - µ, равную

.

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

Для примера рассмотрим модель обслуживания вычислительных заданий в системе рис. 3.11, введя следующие предположения:

1. в системе протекают марковские случайные процессы;

2. потоки событий (появление заданий и окончание их обработки) являются простейшими;

3. число заданий в очереди не ограничено, но кончено.

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

Простейший поток событий характеризуется стационарностью, ординарностью и „без последействием“. Стационарность случайного потока событий означает независимость во времени его параметров (например, интенсивностей l и m). Ординарность указывает на то, что события в потоке появляются по одиночке, а “ без последействия” - на то, что появляющиеся события не зависят друг от друга (то есть поступившее задание не обязано своим появлением предыдущему).

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

Обозначим состояние рассматриваемой вычислительной системы.

S₀ - в системе нет заданий;

S₁ - в системе одно задание и оно обрабатывается на ЭВМ 1;

S₂ - в системе два задания и они обрабатываются на ЭВМ 1 и ЭВМ 2;

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -;

S_n - в системе n заданий и они обрабатываются на ЭВМ 1, ЭВМ 2,..., ЭВМ N;

S_n+1 - в системе заданий, n заданий обрабатываются ЭВМ, а одно стоит в очереди

S_n+2 - в системе заданий, два задания стоят в очереди;

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -;

S_n+m - в системе заданий, m заданий стоят в очереди.

Учитывая, что увеличение числа заявок (заданий) в системе (т.е. номера состояния) происходит под воздействием их потока с интенсивностью l, а уменьшение - под воздействием потока обслуживания с интенсивностью m, изобразим размеченный граф состояний нашей системы. Он показан на рисунке 3.12.

 

Рис. 3.12 Граф состояний многоканальной системы обслуживания с неограниченной очередью

 

Здесь окружности - состояния, дуги со стрелками - направления переходов в следующие состояния. Дуги помечены интенсивностями потоков событий, которые заставляют систему менять состояния. Переходы слева направо увеличивают номер состояния (то есть число заявок в системе), справа налево - наоборот. Как уже указывалось, увеличение числа заявок в системе происходит под воздействием входного потока заявок с постоянной интенсивностью l. Уменьшение числа заявок в системе (уменьшение номера состояния) происходит под воздействием потока обслуживания, интенсивность которого определяется средним временем обслуживания задания одной ЭВМ и числом ЭВМ, участвующих в обработке заданий при данном состоянии системы. Если одна ЭВМ дает интенсивность потока обслуживания m (например, в среднем 30 заданий в час), то одновременно работающие две ЭВМ дадут интенсивность обслуживания 2 m, три ЭВМ - 3 m., „n“ ЭВМ - n m. Такое увеличение интенсивности обслуживания будет происходить вплоть до состояния S_n, когда „ n “ заданий параллельно находятся на обработке на „n“ ЭВМ. Появление в этот момент заявки переводит систему в состояние S_n+1, при котором одна заявка стоит в очереди. Появление еще одной - в состояние S_n+2 и т.д. Интенсивность же потока обслуживания при этом будет оставаться неизменной и равной nm, так как все ЭВМ вычислительной системы уже задействованы.

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

,

где k - число возможных состояний системы;

i - номер состояния.

Для того, чтобы определить значение P_i (t), приведенной формулы не достаточно. Кроме нее составляется еще система дифференциальных уравнений Колмогорова, решение которой и дает искомые значения P_i (t). Чаще всего реальные вычислительные системы быстро достигают установившегося режима, и тогда вероятности состояний перестают зависеть от времени и практически показывают, какую долю достаточно длинного промежутка времени система будет находиться в том или ином состоянии. Например, если система имеет три возможных состояния P₁ =0,2, P₂ =0,6, P₃ =0,1, то это означает, что в состоянии S₁ система в среднем находится 20% времени, в S₂ - 60%, а в S₃ - 10% времени. Такие не зависимые от времени вероятности называют финальными.

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

Это система однородных уравнений (свободный член равен нулю), но благодаря тому, что

система разрешима. Финальные вероятности состояний системы в результате решения описываются следующими математическими отношениями.

где P₀ - вероятность состояния S₀, при котором в системе заявок нет;

- параметр системы, показывающий, сколько в среднем заявок приходит в систему за среднее время обслуживания заявки одной ЭВМ (одним каналом обслуживания).

где P_i -вероятность состояния S_i.

где P_n - вероятность того, что все ЭВМ заняты.

где P_n+j - вероятность того, что все ЭВМ системы заняты обработкой заданий и ‘ j ’ заявок стоят в очереди.

Приведенные формулы имеют смысл только в том случае, если очередь конечна. Условием конечности длины очереди является <1.

Или, если заменить r его выражением через l и m,

.

Практически это выражение говорит о том, что в среднем число заданий, приходящих в вычислительную систему в единицу времени, должно быть меньше числа обрабатываемых заданий в единицу времени всеми ЭВМ системы. Если же , то очередь растет до бесконечности и такая вычислительная система не справится с потоком заданий. Вот тут и могут появиться задания, ожидающие обработки „вечно“.

Основными показателями эффективности рассматриваемой системы являются: среднее число занятых каналов (т.е. ЭВМ) - , среднее число заданий в очереди L_оч и в системе L_сис, среднее время пребывания задания в системе W_сис и в очереди W_оч.

;

;

;

;

.

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

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

Как указывалось, организация очереди, поддержание ее структуры возлагается на диспетчера Д1, а передача заданий из очереди на обработку в вычислительные машины, поддержание дисциплины обслуживания в очереди (поддержка системы приоритетов) осуществляется диспетчером Д2
(рис. 3.11). В вычислительной системе диспетчеры реализуются в виде управляющих программ, входящих в состав операционных систем ЭВМ.

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

 

ОРГАНИЗАЦИЯ ПЛАНИРОВАНИЯ ОБРАБОТКИ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ

 

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

При решении вычислительной задачи ЭВМ использует различные свои ресурсы в объеме и последовательности, определяемыми алгоритмом решения. К ресурсам ЭВМ относятся объемы оперативной и внешней памяти, время работы процессора, время обращения к внешним устройствам (внешняя память, устройства отображения). Естественно, что эти ресурсы ограничены. Поэтому и требуется определить наилучшую последовательность решения поступивших на обработку вычислительных задач. Процесс определения последовательности решения задач во времени называется планированием. Для того, чтобы осуществить планирование, необходимо знать, какие ресурсы и в каком количестве требует каждая из поступивших задач. Анализ потребности задачи в ресурсах производится на основе ее программы решения. Программа состоит, как правило, из ограниченного набора процедур (по крайней мере, к этому стремятся) с известными для данной ВС затратами ресурсов. После анализа поступивших программ решения задач становится ясно, какая задача требует каких ресурсов, и в каком объеме. Наличие этих данных позволяет перейти к планированию вычислительного процесса. Критерии, используемые при планировании, зависят от степени определенности алгоритмов решаемых задач. Крайними случаями являются: а) порядок использования устройств ЭВМ при решении задач строго задан их алгоритмами; б) порядок использования устройств ВС в задачах заранее не известен. Для первого случая приемлемым является критерий минимизации суммарного времени решения вычислительных задач, для второго - максимизации загрузки устройств ВС.

Рассмотрим модель планирования вычислительного процесса при минимизации суммарного времени [28].

Обозначим ресурсы вычислительной системы (ВС) через R₁, R₂, …,R_n. Каждая программа решения задачи обработки данных включает типовые процедуры из набора П₁, П₂, …,П_m. Тогда матрица T ресурсозатрат, приведенных к времени, будет выглядеть, так

,

где - затраты j -го ресурса при выполнении i -й процедуры, i = 1,...., m; j=1,...., n. Знание матриц ресурсозатрат при выполнении программ позволяет вычислить суммарные затраты каждого из ресурсов по всем программам решения вычислительных задач, поступивших в ВС, и составить их матрицу ресурсозатрат. Обозначим поступившие в ВС программы решения задач через З₁, З₂, …,З_m; t_ij - затраты j - го ресурса, приведенного к времени, на выполнение i - й задачи (i=1,....,m; j=1,....,n); R₁, R₂, …,R_m - ресурсы ВС. Матрица ресурсозатрат по задачам запишется в виде

.

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

1) для любого устройства ВС выполнение последующей вычислительной задачи не может начаться до окончания предыдущей;

2) каждое устройство в данный момент может выполнять только одну вычислительную задачу;

3) начавшееся выполнение задачи не должно прерываться до полного его завершения.

Если в процессе обработки данных используется „ n “ устройств (ресурсов) ВС, нахождение оптимальной последовательности поступающих на решение „ m “ задач, минимизирующих суммарное время обработки, потребует перебора (m!)ⁿ вариантов. Например, если в ВС поступило всего 6 заданий (m =6), использующих всего 2 ресурса (n =2), то для нахождения оптимальной последовательности, после составления матрицы T_n, потребуется произвести (6!)² переборов, т.е. 518400. Если же m =10, то потребуется порядка 10¹³ переборов. Ясно, что даже для ЭВМ это многовато.

Алгоритм Джонсона, полученный для n =2, требует перебора только m(m+1)/2 вариантов. То есть для нашего примера (m =6) необходимо будет проделать 21 перебор, что значительно меньше, чем 518400. При n >2, задачу планирования по критерию минимума суммарного времени обработки, сводят к задаче Джонсона путем преобразования матрицы T_n. Например, если n =3 (то есть три ресурса), то производится попарное сложение первого и второго, второго и третьего столбцов, и таким образом получают двухстолбцовую матрицу T_n. После преобразования следует проверить, выполняются ли вышеперечисленные условия. Если это не так, то задача планирования не имеет строгого решения, и используют эвристические алгоритмы.

Для пояснения алгоритма Джонсона представим матрицу T_n как двухстолбцовую:

.

Алгоритм Джонсона состоит в следующем:

1. В матрице T_n определяется t_min = min{t₁₁, t₁₂, …,t_m2}.

2. Из задач З₁, …,З_m выбираются задачи, для которых ресурсоемкость хотя бы по одному устройству была равна t_min, т.е. выбирают задачи З_i, у которых хотя бы одна из двух t_ij = t_min. (Напомним, что i- это номер задачи, j - номер устройства, i=1,...., m, j=1;2).

3. Задачи группируют по минимальному времени их исполнения t_min на первом и втором устройствах, т.е. З_i(t_min, t_i2) и З_i(t_i1, t_min).

4. В начало последовательности обрабатываемых задач ставят З_i(t_min, t_i2) в конец - З_i(t_i1, t_min).

5. Вставленные в последовательность задачи исключаются из матрицы T_n.

6. Для новой матрицы повторяются пункт (1-3).

7. Задачи З_i(t_min, t_i2), З_i(t_i1, t_min), полученные из новой матрицы, ставятся в середину составленной ранее последовательности и т. д.

В основе эвристических алгоритмов лежат процедуры выбора из поступивших задач наиболее трудоемких и расположения их в порядке убывания времени выполнения.

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

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

Таким образом, одной из важнейших процедур информационного процесса обработки данных является организация вычислительного процесса, которая выполняет функции обслуживания поступающих на обработку заданий (очередей) и планирования (оптимизации последовательности) их обработки. На программно-аппаратном уровне эти функции выполняют специальные управляющие программы, являющиеся составной частью операционных систем, то есть систем, организующих выполнение компьютером операций обработки данных. Разнообразие методов и функций, используемых в алгоритмах организации вычислительного процесса, зависит от допустимых режимов обработки данных в ВС. В наиболее простой ВС, такой как персональный компьютер (ПК), не требуется управление очередями заданий и планирование вычислительных работ. В ПК применяют, в основном однопрограммный режим работы. Поэтому их операционные системы не имеют в своем составе программ диспетчерирования, планировщика и супервизора. Но в более мощных ЭВМ, таких как серверы и, особенно, мэйнфреймы, подобные управляющие программы оказывают решающее влияние на работоспособность и надежность ВС. Например, к UNIX-серверам могут обращаться с заданиями одновременно сотни пользователей, а к мэйнфреймам типа S/390-тысячи.

 

ПРЕОБРАЗОВАНИЕ ДАННЫХ

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

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

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

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

 

 

Рис. 3.13 Граф преобразования данных

 

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

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

На пересечении строки и столбца ставится „1“, если операция и информационный элемент связаны. Другими словами получим матрицу L.

. ,

где l_ij=1 - если информационный элемент D_j используется при выполнении операции A_i;

l_ij= 0 - в противном случае;

l_ij=0 -в противном случае;

i=1,...,m; j=1,...,n.

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

Данная задача может быть сведена к задаче линейного программирования и решена с использованием стандартных прикладных программ.

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

Граф - схема алгоритма представляет собой древовидный граф, узлами которого является операции над данными, а дугами - связи (отношения) между операциями в алгоритме. Операции в алгоритме выполнятся последовательно-параллельно, так что в корне графа расположена головная (начальная) операция A₀, от которой после ее выполнения происходит переход к операции A₁ или А₂, затем к А₃, А₄,..., А_m. (рис.3.14).

 

 

Рис. 3.14 Граф-схема алгоритма

 

Приведенный граф можно разместить, написав возле дуг число обращении r_ij от операции А_i к операции А_j (например, от А₁ к А₃) в процессе выполнения алгоритма. Число обращений в детерминированных алгоритмах r_ij ³1, для вероятностного алгоритма число r_ij <1,так как оно определяет вероятность обращения операции А_i к операции А_j. При анализе алгоритмов решения вычислительных задач, можно выделить общие совокупности операций (пересечения граф-схем). На рис. 3.15 алгоритмы P₁ и P₂ имеют три общие операции, составляющие подмножество операций, входящих одновременно и в множество операций алгоритма P₁, и в множество операций алгоритма P₂ (заштрихованная часть рис.3.15)

 

Рис. 3.15 Объединение граф-схем алгоритмов

 

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

 

Рис. 3.16 Фрагмент вычислительного графа программной системы

 

Здесь головным является вычислительный модуль М₀. Ему подчинены модули, находящиеся на нижележащих уровнях. На самом нижнем уровне расположены модули, выполняющие элементарные типовые операции.

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

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