Составители:
Рубрика:
Глава 5. АЛГОРИТМЫ И ВЫЧИСЛИТЕЛЬНЫЕ
СИСТЕМЫ
§ 1. О соотношении графов алгоритма
и вычислительной системы
Вычислительные системы будем представлять графами, вер-
шинам которых поставлены в соответствие функциональные
устройства, а направленные дуги соответствуют направлениям пе-
редачи информации от одного устройства к другому. В отличие от
вычислительного алгоритма граф вычислительной системы может
иметь контуры.
Вычислительную систему описывают три основные компонен-
ты:
— множество функциональных устройств;
— коммуникационная сеть, обеспечивающая обмен информа-
цией между устройствами;
— множество допустимых программ работы всей совокупности
функциональных устройств.
Будем предполагать, что все временные затраты определя-
ются затратами на обеспечение функционирования рассматрива-
емых функциональных устройств, работающих по заданной про-
грамме; время на передачу информации от одного функциональ-
ного устройства к другому не принимается во внимание (последнее
предположение не уменьшает общности рассмотрения, ибо в случае
необходимости канал передачи можно рассматривать как функци-
ональное устройство).
Замечание. Одна и та же вычислительная система может ре-
ализовывать как различные алгоритмы, так и один и тот же алго-
ритм, но в различных временных режимах.
Для указания конкретной реализации алгоритма необходимо
задать программу работы всей совокупности устройств, а именно:
— перед каждым срабатыванием любого функционального уст-
ройства определены функциональные устройства, поставляющие
данные и потребляющие результат;
— указаны моменты включения функциональных устройств
(моменты начала выполнения каждой операции);
— в момент включения каждого функционального устройства
определены тип операции и время ее выполнения (эта характери-
66
Страницы
- « первая
- ‹ предыдущая
- …
- 63
- 64
- 65
- 66
- 67
- …
- следующая ›
- последняя »
