Параллельные вычисления

Иерархия языков

Продукции позволяют осуществлять самые pазные трансформации строк. Чаще всего языки делят на четыре типа, в зависимости от ограничений, налагаемых на грамматику.

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

Простейшим ограничением является требование, чтобы правая часть каждой продукции имела по крайней мере столько же символов, что и левая. Грамматика такого вида называется грамматикой типа 1 или неукорачивающей контекстно-зависимой грамматикой.

Если левая часть продукции ограничивается одним нетерминальным символом, то ее применение не зависит от контекста, в котором этот символ появляется в исходной строке. Грамматика с таким ограничением называется грамматикой типа 2 или контекстно-свободной грамматикой.

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

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

Язык называется регулярным, если он может быть порожден праволинейной или леволинейной грамматикой.

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

Одним из путей обхода ограничения скорости явялется перестройка вычислительных систем на параллельное выполнение большого числа операций.

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

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

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

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

Имеется много численных методов, которые нельзя эффективно реализовать ни на каких многопроцессорных системах.

Следующая идея повышения быстродействия – организация конвейера.

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

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

РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА

1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988. - 480с.

2. Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2001. - 304 с.

3.Донской В.И. Дискретная математика. - Симферополь.:Сонат,2000.-360 с.

4.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1975.- 240 c.

5. Грэй П. Алгебра, логика и базы данных: Пер. с англ. - М.: Машиностроение, 1989. - 260 с.

6. Акимов О.Е. Дискретная математика. Логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001. – 376 с.

7. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. - М.: Лаборатория Базовых Знаний, 2002. – 288 с.

8. Кэррол Л. История с узелками: Пер. с англ. - М.: Мир, 1973. - 408 c.

9. Оре.О. Теория графов: Пер. с англ. – М.: Наука, 1968. – 310 с.

10. Форд Л., Фалкерсон Д. Потоки в сетях: Пер. с англ. – М.: Мир, 1966. – 288с.

11. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы: Пер. с англ. – М.: Вильямс, 2000. – 382 с.

12. К. Шеннон. Работы по теории информации и кибернетике. – М.: Ин. лит., 1963. - 654 с.

13. А. М. Яглом, И. М. Яглом. Вероятность и информация. – М.: Наука, 1973. – 512 с.

14. И. В. Кузьмин., В. А. Основы теории информации и кодирования. – К.: В. Шк., 1986. – 218 с.

15. В. П. Цымбал. Теория информации и кодирования. К.: В. Шк., 1992. – 224с.

16. Романец Ю.В., Тимофеев П. А., Шаньгин В.Ф. Защита информации в компьютеных системах и сетях. - М.: Радио и связь, 1999. – 328 с.

17. Фор Р., Кофман А., Дени-Папен М. Современная математика. М.: Мир, 1966.

18. Новиков П.С. Элементы математической логики. М.: Наука, 1973.

19. Трахтенброт Б.А., Бардзинь Я.М. Конечные автоматы (Пове­дение и синтез). М.: Наука, 1970.

20. Берж К. Теория графов и её применения. М.: Изд. иностр.ли­тературы, 1962.

21. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Тео­рия, методы и приложения. М.: Наука, 1969.

22. Донован Дж. Системное программирование. М.: Мир, 1975.

23. Клини С.К. Математическая логика. М.: Мир, 1973.

24. Минский М. Вычисления и автоматы. М.: Мир, 1971.

25. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Сов. радио, 1974.

Дата добавления: 2014-01-06