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

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

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

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

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

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

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

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

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

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

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

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

Книга состоит из трёх частей.

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

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

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

В конце книги приведён граф моделей ЭВМ, который служит предметным указателем.

Авторы

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

Чтобы иметь возможность решать конкретные задачи, возникающие в процессе проектирования, необходимо в каждом случае отвлекаться от второстепенных деталей, рассматривая только то, что является наиболее существенным для данной задачи. Таким образом, формируются различные математические модели вычислительных устройств и их взаимодействия. Различие этих моделей определяется их назначением для различных этапов проектирования вычислительных машин [20]: системного, программного обеспечения, логического, технического, электронных схем.

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

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

Под системой массового обслуживания (СМО) в настоящее время понимают [23, 38] время-логическую систему, представляющую собой единство трёх категорий:
1) входящего потока заявок или требований на обслуживание;
2) параметров обслуживающих приборов или узлов;
3) дисциплины обслуживания заявок, находящихся в системе.

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

Первые две категории СМО являются временными категориями. Они описываются регулярными или вероятностными соотношениями, определяющими время между поступлениями заявок в систему и время обслуживания заявки в приборе.

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

Прежде всего остановимся на методах описания временных категорий.

Получив функциональную модель работы ЭВМ, следует определить её математическую модель, рассматриваемую как систему массового обслуживания.

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

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

Как правило, на этапе проектирования структуры приходится иметь дело с её существенно упрощёнными моделями. Это в свою очередь несколько упрощает решение вопроса о точности модели потока команд.

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

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

При такой постановке модели структур ЭВМ можно рассматривать как системы массового обслуживания.

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

Возможны две дисциплины работы системы, обусловленные появлением заявки на выходе первого узла А₁, когда накопитель полностью заполнен заявками, а именно:

1. Узел А₁ прекращает генерировать заявки и хранит уже обслуженную им заявку до тех пор, пока не освободится место в накопителе Б, т.е. пока узел А₂ не обслужит свою очередную заявку.

2. Заявка, обслуженная узломА₂, теряется, а узел А₁ сразу же начинает обслуживать следующую заявку.

При исследовании «внутренней» производительности ЭВМ наиболее типична первая ситуация, хотя, например, исследование функционирования модели структуры «Память на магнитном барабане – оперативная память» в ряде случаев приводит ко второй дисциплине работы.

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

Системы массового обслуживания с потерями заявок при конечной ёмкости накопителя изучались, например, в [8], а также [67] – GI | M | 1 | n и в [70] – M | G | 1 | n (период занятости системы). Здесь приняты модифицированные обозначения Кендалла [8, 36] (п – ёмкость накопителя).

Системы массового обслуживания первого типа (с блокировкой) с нулевой ёмкостью накопителя исследовались в [3] при произвольном виде функций распределения обслуживания заявок узлами (см. гл. 6). При конечной ёмкости накопителя, когда одна из функций распределения произвольна, а другая экспоненциальна, имеется рекуррентное решение [4–6] (см. гл. 2); отметим и [76], по постановке близкую к рассматриваемой модели. Будем обозначать СМО второго типа как F₁–n–F₂, где F₁ и F₂ – функции распределения длительности обслуживания заявок первым и вторым узлами соответственно, а n – ёмкость накопителя заявок между узлами.

Предположение по пп. 1–6 § 4-1 определяет первую дисциплину работы системы. Переход ко второй дисциплине осуществляется заменой предположения п. 6 на следующее: если при появлении заявки на выходе узла А₁ в накопителе нет ни одного свободного места, то эта заявка теряется и узел А₁ начинает сразу же обслуживать следующую заявку. Такие системы, как было указано выше, называются системами массового обслуживания с потерями.

Итак, рассмотрим систему массового обслуживания с потерями заявок с одним обслуживающим узлом А, функция распределения времени обслуживания заявок которого произвольна F(t) (или эрланговская f(t) = γ(γt) ^k − 1 e^− γt ⁄ (k − 1)!), и рекуррентным потоком поступления заявок, длительность интервала между последовательным поступлением заявок подчиняется эрланговскому распределению γ(γt) ^k − 1 e^− γt ⁄ (k − 1)! [или произвольной функции распределения F(t)] и ёмкостью накопителя Б, т.е. в обозначениях Кендалла [36] системы E_k | G | 1 | n (GI | E_k | 1 | n).

Простейшими моделями, описывающими процесс обработки информации в системе память – АЛУ (П–А), являются двухфазные модели, примеры которых приведены в гл. 2. Узел П (см. рис. 2-1) в таких моделях является моделью узла памяти, работающего в режиме считывания операндов. Узел А является моделью АЛУ. Двухфазные модели предполагают, что фаза записи в процессе обработки информации отсутствует. Это весьма жёсткое ограничение оправдывается только тогда, когда ЭВМ содержит СБЗУ достаточно большой ёмкости и можно пренебречь малой вероятностью записи промежуточных результатов в стационарном режиме работы машины. Однако двухфазные модели позволяют во многих случаях получить результаты в аналитической форме, удобной для исследования влияния изменения параметров статистических моделей потока команд. Кроме того, порядок изложения от простого к сложному наиболее рационален для понимания существа исследуемого вопроса и сути полученных результатов.

Общий случай двухфазной модели представлен на рис. 6-1. Здесь П – модель узла памяти, генерирующая заявки (первая фаза). Время генерации одной заявки этим узлом τ₁ случайное и подчиняется закону распределения F₁(t) = P (τ₁ > t). Моделью АЛУ служит узел А, закон распределения случайного времени обслуживания заявок этим узлом F₂(t). Перед второй фазой обслуживания заявок узлом А заявки образуют очередь в накопителе очередей Б ёмкостью n заявок. Узел А берёт на обслуживание (поглощает) из накопителя очередей i заявок с вероятностью ρ_i (i = 0, 1, …, l) (см. ρ-распределение, гл. 3).
 

┌─────────────┐   │      ┌──────┤ ν ▼    ρ ▼      │ ┌─┴─┐  ┌─┴─┐  ┌─┴─┐ │ П ├─►┤ Б ├─►┤ А │ └───┘  └───┘  └───┘

Рис. 6-1. Общий случай двухфазной модели.

Заявка, обслуженная узлом А, покидает систему и при этом с вероятностью ν может потребовать уничтожения заявок, находящихся в накопителе и узле П (модель условного перехода по неугаданному направлению).

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

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

Описанная модель при общих предположениях о распределениях F₁(t) и F₂(t) не поддаётся аналитическим методам исследования, изложенным в гл. 2. Поэтому остановимся иа частных случаях, представляющих самостоятельный интерес и дающих возможность оценить эффективность аналитических методов исследования процессов выполнения команд в ЭВМ.

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

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

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

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

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

Там же построена статистическая модель МП, при более детальном изучении структур ЭВМ эта модель требует дополнительного уточнения.

Настоящая глава посвящена исследованию связи числа команд в программе, реализующей алгоритм, с интерпретацией кода команды. Рассмотрим такую команду двухадресной ЭВМ, как, например, сложение. Команда может предполагать следующее: 1) операнды находятся в ячейках ЗУ с адресами, указанными в ней, а результат записывается в сумматор; 2) один операнд находится в сумматоре, а другой – в ячейке ЗУ с адресом, указанным в первом адресе команды, результат же записывается в ячейку с адресом, указанным во втором адресе данной команды.

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