BC/NW 2017 № 2 (31):2.2

УЧЕТ ОСОБЕННОСТЕЙ ВЫПОЛНЕНИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

Филатов А.В.

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

 

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

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

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

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

 

Рис. 1. Пример графа эквивалентных алгоритмов решения задачи

 

Граф представляет собой развёрнутые по времени слева-направо альтернативные последовательности выполнения макро-действий (определение будет дано позже) эквивалентных алгоритмов. Каждый алгоритм статически описывает порядок выполнения необходимого множества MA макро-действий (в графе представлены вершинами):

 

MA={ma0, ma1, ma2, ma3, … }.

 

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

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

Представим вычислительную систему множеством устройств:

 

SYSTEM={unit0, unit1, unit2, unit3, … }.

 

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

 

C={c0, c1, c2, c3, … }.

 

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

 

Рис. 2. Пример вычислительной системы и распределения классов действий по её устройствам

 

При выполнении вычислительного процесса, каждое макро-действие выполняется совокупностью реальных действий устройств вычислительной системы. То есть, каждое макро-действие реализуется совокупностью реальных действий. Такая реализация также описывается алгоритмом. Назовём его исполнительным алгоритмом.  Одно и то же макро-действие может быть реализовано несколькими альтернативными алгоритмами. Каждый из исполнительных алгоритмов выбирается на выполнение в зависимости от сложившихся условий. Например, макро-действие – загрузка данных. Если данные находятся в КЭШ-памяти, то исполнительный алгоритм один; если данные находятся в оперативной памяти вне КЭШ, то исполнительный алгоритм другой; если данные находятся в удалённой оперативной памяти, то исполнительный алгоритм третий; если данные находятся во внешней памяти, то исполнительный алгоритм четвёртый. Таким образом, для каждого i-го макро-действия можно составить граф альтернативных исполнительных алгоритмов. Пример такого графа приведён на рис. 3. 

 

 

Рис.3. Пример графа альтернативных исполнительных алгоритмов для i-го макро-действия.

 

Граф представляет собой развёрнутые по времени слева-направо альтернативные последовательности выполнения действий для реализации i-го макро-действия (mai), согласно исполнительным алгоритмам. Каждое действие любого из альтернативных исполнительных алгоритмов (0, 1, 2, 3, …) представлено вершиной и входит в множество A-действий.

 

A={a0, a1, a2, a3, … }.

 

Вершины действий в графе взвешены двумя показателями. Каждое действие относится к какому-либо классу из множества C, и каждое действие каждого из алгоритмов характеризуется некоторым коэффициентом из множества K:

 

K={k0, k1, k2, k3, … }.

 

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

 

Теперь посмотрим это всё на примере задачи. Пусть имеются два массива: X – двухмерный, размером 4x4 и Y – одномерный, размером в 4 элемента. Пусть надо получить двухмерный массив Z размером 4x4 со следующим значением элементов: Z_nm=X_nmY_n.

На рис. 4. Показан граф с двумя эквивалентными алгоритмами решения задачи. Макро-действия в обоих алгоритмах показаны наглядно. Оба алгоритма эквивалентны, то есть при одинаковых исходных данных, дают одинаковые вычислительные результаты. Отличие между алгоритмами заключается во вложенных циклах. В алгоритме 0 цикл по n внутренний, а по m – внешний. В алгоритме 1 внутренний цикл по m, а внешний по n. Оба алгоритма выполняют одинаковое количество одних и тех же макро-действий.

 

Рис.4. Граф эквивалентных алгоритмов решения задачи

 

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

 

Рис. 5. Граф альтернативных исполнительных алгоритмов для операции умножения

 

В графе представлены два исполнительных алгоритма. Они отличаются тем, что в нулевом сначала оба операнда загружаются из массивов X и Y в регистры R0 и R1 соответственно, а в первом алгоритме только одна загрузка (в регистр R0 загружается операнд из X), поскольку операнд из Y уже есть в регистре R1 после предыдущего выполнения операции умножения. Загрузка операнда взвешена коэффициентом 10. Пусть для примера это будут машинные такты. Если внимательно проследить выполнение эквивалентных алгоритмов (см. рис. 4), то при использовании алгоритма 0, для операции умножения все 16 раз будет вызван исполнительный алгоритм 0 (см. рис. 5), а при использовании алгоритма 1 (см. рис. 4), для операции умножения исполнительный алгоритм 0 (см. рис. 5) будет вызван 4 раза, а исполнительный алгоритм 1 будет вызван 12 раз. Таким образом, можно предположить, что при выполнении вычислительного процесса согласно алгоритму 1 (см. рис. 4), решение задачи будет на 120 машинных тактов получено раньше, чем при выполнении вычислительного процесса согласно алгоритму 0.     

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

 

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