Введение в архитектуру компьютеров


Направления повышения эффективности компьютеров - часть 5


*                   модели, базирующиеся на сетях Петри и схемах синхронизации, и т. д.

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

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

В теории параллельных вычислений имеется ряд открытых проблем. Основная из них – это возможность эффективного распараллеливания алгоритмов. Она формулируется как соотношение классов NC и P. Это вопрос такой же важности, как соотношение классов P и NP в теории сложности вычислений, и очень далек от своего решения, ибо предполагает получение сверхполилогарифмических оценок параллельной сложности решения некоторых задач из класса P.

К конкретным задачам, для которых неизвестна их принадлежность ни к NC, ни к P-классу, относится, например, задача возведения целого в степень: для заданных n-битовых чисел a, b

и m вычислить ab mod m.




- Начало -  - Назад -  - Вперед -



Книжный магазин