Быстродействие ЭВМ повышалось за счет увеличения скорости срабатывания логических элементов. За последние десятилетия скорость выполнения операций и взаимодействия с памятью возросла на несколько порядков. Дальнейшее увеличение скорости стало ограничиваться причинами физического характера.
Одним из путей обхода ограничения скорости явялется перестройка вычислительных систем на параллельное выполнение большого числа операций.
Пусть при решении некоторого класса задач удалось заставить каким-то образом каждый процессор выполнять полезную работу и при этом использовать каждое устройство памяти. При благоприятных условиях можно рассчитывать на пропорциональное числу процессоров и числу устройств памяти увеличение эффективности. Эта идея привела к развитию многопроцессорных систем, структурированных процессоров для обработки массивов, ассоциативных процессоров и конвейерных процессоров: eсли ЭВМ с одним процессором и с одним устройством памяти не удовлетворяет потребностям решения, то возьмем несколько устройств памяти, несколько процессоров и объединим их в единую систему, связав каналами передачи информации.
Не возникло бы проблем, если бы большое число устройств всегда можно было бы связать коммуникационной сетью, обеспечивающей передачу информации между устройствами со скоростью, существенно превышающей скорость переработки информации процессорами или хотя бы соизмеримой с ней. Пока таких коммуникационных сетей нет.
Прямая связь каждого устройства с каждым приводит к резкому усложнению сети с ростом числа устройств.
За краткую историю параллельных вычислений выработалось эмпирическое правило, называемое эффектом Амдаля: для достаточной эффективности вычислений на параллельной машине с m процессорами вычисления должны распадаться на m потоков данных, причем нужно, чтобы последовательно выполнялась существенно меньшая, чем 1/m доля сегментов. Эффект Амдаля основан на отсутствии внутреннего параллелизма в большинстве современных программ.
Имеется много численных методов, которые нельзя эффективно реализовать ни на каких многопроцессорных системах.
Следующая идея повышения быстродействия – организация конвейера.
Процесс выполнения операции в процессоре распадается реально на ряд этапов. В общем случае при реализации одной операции в каждый момент времени работает только одно из устройств, остальные простаивают из-за отсутствия работы. Положение меняется, если нужно выполнить не одну операцию а большое их число, причем не зависящих друг от друга. По принципу конвейера не нужно ждать окончания всего процесса выполнения предыдущей операции, достаточно, чтобы у нее был закончен первый этап. Реализация конвейера позволяет максимально загрузить процессор выполнением полезной работы. Однако за это приходится платить необходимостью организовывать данные специальным образом, объединяя в отдельные потоки независимые однотипные операции.
Если при реализации какого-либо алгоритма можно так организовать вычисления, что все функциональные устройства будут загружены выполнением полезной работы, то в целом на данной вычислительной системе будет достигнута максимально возможная, при данном составе устройств, скорость решения задачи.
Л И Т Е Р А Т У Р А
1. Фор Р., Кофман А., Дени-Папен М. Современная математика. М.: Мир, 1966.
2. Новиков П.С. Элементы математической логики. М.: Наука, 1973.
3. Трахтенброт Б.А., Бардзинь Я.М. Конечные автоматы (Поведение и синтез). М.: Наука, 1970.
4. Берж К. Теория графов и её применения. М.: Изд. иностр.литературы, 1962.
5. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения. М.: Наука, 1969.
6. Донован Дж. Системное программирование. М.: Мир, 1975.
7. Клини С.К. Математическая логика. М.: Мир, 1973.
8. Минский М. Вычисления и автоматы. М.: Мир, 1971.
9. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Сов. радио, 1974.
Оглавление
1. ТЕОРИЯ АЛГОРИТМОВ
1.1. Основные понятия
1.1.1 Основные требования к алгоритмам
1.1.2. Блок–схемы алгоритмов
1.1.3. Представление данных
1.1.4. Виды алгоритмов
1.1.5. Правильность программ
1.1.6.Эффективность алгоритмов
1.1.7. Сходимость, сложность, надежность
2. Универсальные алгоритмы
2.1. Основные понятия
2.2. Машины Тьюринга
2.3. Рекурсивные функции
2.4.ПР-операторы
2.5. Тезис Черча-Тьюринга
2.6. Проблема самоприменимости
3. Формальные системы
3.1. Метатеория логических исчислений
3.2. Абстрактные формальные системы
4. Языки и грамматики
4.1. Общие понятия
4.2. Формальные грамматики
4.3. Иерархия языков
5. Параллельные вычисления
Л И Т Е Р А Т У Р А
Оглавление