Модель вычислений
Модель вычислений (computing model, computational model, model of computation): модель вычислительного оборудования, способного исполнять программу (алгоритм). Модели такого рода характеризуются степенью подробности и степенью абстрагированности (отвлечённости) описания от реального оборудования и используются для разработки и исследования программ и алгоритмов.[1],[2]
Содержание
Последовательные вычисления
В случае последовательного вычисления на цифровом оборудовании все вычислительные модели имеют в основе модель архитектуры фон Неймана и различаются лишь уровнем абстрагированности от неё. Примерами таких моделей являются равнодоступная адресная машина (РАМ), равнодоступная адресная машина с хранимой программой (РАСП), машина Тьюринга.[1] Столь большая схожесть моделей последовательного вычисления не позволила выработать для них общепринятые классификации моделей (по замечанию 1992 года)[2].
Параллельные вычисления
В случае параллельных вычислений предложена (1992) классификация моделей параллельных вычислений, определяющая четыре класса (уровня): модель машины, модель архитектуры, модель расчёта, модель программирования[2]. Существуют и другие, подобные классификации моделей параллельных вычислений[3].
Модель машины
Модель машины (machine model): модель наинизшего уровня отвлечённости (абстрактности). Рассматривает вычислительное оборудование как собственно оборудование совокупно с операционной системой.[2]
Например, программирование на ассемблере можно считать использующим этот уровень моделей вычислений.[2]
Модель архитектуры
Модель архитектуры (architectural model): модель следующего уровня отвлечённости; описывает обобщённые характеристики (конкретных экземпляров) оборудования и операционной системы.[2]
Например, для последовательных ЭВМ (с одним исполняющим устройством) архитектура описывается моделью фон Неймана. Для параллельного вычислительного оборудования (ПарВМ) описывается топология внутренней сети, но не её аппаратное осуществление, синхронность ПарВМ, соответствие одному из классов Флинна, общая организация рабочей памяти (общая или распределённая).[2]
Модель расчёта
Модель расчёта (по-английски, как и модели вычислений вообще, называется computational model или model of computation): модель следующего уровня отвлечённости; описывает обобщённые характеристики целого класса вычислительного оборудования, рассматриваемого по его модели архитектуры.[2]
Например, в случае последовательного расчёта модель РАМ[1] это широко распространённая модель для исследования алгоритмов; имеет в своей основе модель архитектуры фон Неймана.[2]
Примеры моделей параллельного расчёта: ПРАМ, параллельная равнодоступная адресная машина (PRAM — parallel random access machine): обобщение модели РАМ; BSP (bulk synchronously parallel): абстракция параллельной выч. машины с физически распределённой памятью и пакетными передачами между процессорами; LogP: модель, призванная исправить недостатки модели ПРАМ и учитывающая временной фактор в передачах данных.
Поскольку модель расчёта используется обычно в теоретической работе, модель такого уровня также называют абстрактной или формальной моделью – имея в виду, что оборудование в ней не описывается даже столь обобщённо, как в модели архитектуры. Соответственно, в отношении последовательных вычислений модели расчёта и архитектуры могут и не различаться, или различаться лишь по наличию на уровне модели расчёта дополнительных характеристик наподобие стоимости действия. Однако, например, модель параллельного расчёта ПРАМ уже не может быть воплощена в реальной архитектуре параллельного вычислительного оборудования, и на реальном оборудовании её работа лишь имитируется.[2]
Модель программирования
Модель программирования (programming model): модель следующего уровня отвлечённости; описывает вычислительное оборудование в понятиях семантики конкретного языка программирования.[2]
Одно из ключевых различий с моделью расчёта: модель расчёта рассматривает память как последовательность ячеек, а модель программирования – как структуру данных (определённых в языке программирования), возможно сложную.[2]
— Ю.Т.
Источники
- Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман ; пер. с англ. А.О. Слисенко ; под ред. Ю.В. Матиясевича. – М. : Мир, 1979. – 536 с.
- A practical hierarchical model of parallel computation: the model / T. Heywood, S. Ranka // J. Parallel Distr. Comp. – 1992. – V. 16, № 3. – P. 212–232.
- A survey of models of parallel computation : technical report YCS-97-278 / D.K.G. Campbell ; Department of Computer Science; University of York. York, UK : University of York, 1997.
