|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[214] 30.3.1. Упражнения 30.3-1. Докажите результат, аналогичный теореме Брента, для моделирования на CRCW-машине схем, содержащих элементы И и ИЛИ с любой входной степенью. (Указание: в качестве размера следует рассмотреть общее количество входов элементов). 30.3-2. Докажите, что существует EREW-алгоритм для параллельной обработки префиксов массива из га элементов, использующий О (га/ lgra) процессоров и имеющий время работы О (lgra). Почему этот алгоритм нельзя использовать для списков? 30.3-3. Постройте эффективный по затратам алгоритм для умножения матрицы размера га X га на вектор размера га со временем работы О (lgra). (Указание: Постройте сначала схему из функциональных элементов.) 30.3-4. Постройте CRCW-алгоритм для умножения двух матриц размера га X га, использующий га2 процессоров и не менее эффективный по затратам, чем стандартный алгоритм со временем работы 0(га3). Будет ли он EREW-алгоритмом? 30.3-5. В некоторых моделях параллельных вычислений процессоры могут отключаться на некоторых шагах, так что число активных процессоров уменьшается. При подсчёте затрат на каждом шаге учитываются только активные процессоры. Докажите, что CRCW-алгоритм в такой модели со временем работы t, затратами w и любым начальным числом процессоров может быть смоделирован на EREW-машине с р процессорами за время 0((w/p-\-t) lgp). (Основная сложность состоит в том, что заранее неизвестно, какие процессоры будут активны.) 30.4. Эффективная параллельная обработка префиксов В разделе 30.1.2 был рассмотрен EREW-алгоритм параллельной обработки префиксов для списка из га элементов за время О (lgra). Он использует га процессоров, поэтому затраты составляют ©(ralg га), что больше, чем затраты О (га) однопроцессорного алгоритма. Следовательно, алгоритм List-Prefix не является эффективным по затратам. В этом разделе описывается вероятностный EREW-алгоритм параллельной обработки префиксов, который использует ©(га/lgra) процессоров и в большинстве случаев (с большой вероятностью) работает за время О (lgra). Таким образом, этот (вероятностный) алгоритм можно считать эффективным по затратам. Конструкция теоремы 30.4 позволяет указать такой алгоритм для любого числа процессоров р = 0(п/ lg га). splice out = удаление splice in = возвращение удалённых рекурсивный вызов процедуры Randomized-List-Prefix Рис. 30.9 30.9. Рекурсивный вероятностный алгоритм обработки префиксов списка на примере списка из 9 объектов, (а) Чёрные объекты намечены для удаления. (Среди них нет соседних.) (Ь) Значение каждого удаляемого объекта соединяется со значением следующего; алгоритм рекурсивно вызывается на уменьшенном списке, (c)-(d) В результате уцелевшие элементы получают правильные значения, а удалённые объекты вычисляют свои префиксы с помощью предыдущих. splice out удаление splice in возвращение stage 1 уровень 1 (bottom) (внутренний) (top) (внешний) Рис. 30.10 30.10. Уровни рекурсии для алгоритма Randomized-List-Prefix. Вначале список содержит 9 объектов. Рекурсивные вызовы осуществляются до тех пор, пока список не станет пустым. 30.4.1. Рекурсивная параллельная обработка префиксов Алгоритм Randomized-List-Prefix использует для га-элементного списка р = 0(ra/lgra) процессоров, так что каждый процессор отвечает за п/р = в (lgra) элементов. Распределение объектов по процессорам происходит произвольным образом (не обязательно подряд) в начале работы алгоритма и более не меняется. Для удобства будем считать, что список является двунаправленным, поскольку такой список можно изготовить из однонаправленного за время 0(1). Идея алгоритма состоит в том, чтобы исключить из списка некоторые объекты (присоединив их к следующим за ними), произвести обработку префиксов для получившегося списка, а затем обработать пропущенные префиксы, учтя исключённые элементы. Один уровень рекурсии показан на рис. 30.9, а весь процесс - на рис. 30.10. При выборе исключаемых элементов мы будем соблюдать такие правила:: 1.Нельзя одновременно исключать два элемента, за которые отвечает один и тот же процессор. 2.Нельзя исключать два соседних в списке объекта. Перед тем как описывать механизм выбора исключаемых элементов, рассмотрим подробнее сам процесс исключения. Пусть решено исключить /г-й объект. Тогда (/г + 1)-й объект запоминает значение [к, /г+1] = [к, к] <g> [к + 1, к + 1] (после чего /г-й объект удаляется). Если /г-й объект является последним, то он просто удаляется из списка. После удаления процедура Randomized-List-Prefix вызывает саму себя на уменьшенном списке, если он ещё не пуст. После этого рекурсивного вызова все элементы уменьшенного списка содержат правильные значения префиксов, и остаётся лишь обработать префиксы, соответствующие исключённым элементам. Это сделать легко: если /г-й объект был исключён, то (к - 1)-й объект остался в списке и после рекурсивного вызова содержит значение [1, к - 1]. Остаётся лишь вычислить [1, к] = [1, к - 1]®[/г, к]. Условие 1 гарантирует, что для каждого исключённого объекта найдётся процессор, который будет производить вычисления. Условие 2 обеспечивает возможность обработать недостающий префикс, произведя всего одну операцию <g> (см. упр. 30-4.1). Итак, при выполнении требований 1 и 2 каждый шаг алгоритма требует времени 0(1). 30.4.2.Выбор удаляемых объектов Как же выбирать объекты для удаления? Прежде всего, необходимо соблюдать требования 1 и 2. Кроме того, сам процесс выбора должен занимать немного времени (лучше всего 0(1)). Наконец, следует удалять как можно больше объектов, чтобы остающийся список был как можно короче и глубина рекурсии - как можно меньше. Укажем способ удовлетворить всем этим требованиям. 1.Каждый процессор случайно выбирает один из подведомственных ему объектов (из числа оставшихся в списке). 2.Каждый процессор бросает монету и с вероятностью 1/2 помечает выбранный им на предыдущем шаге объект (а с вероятностью 1/2 не делает ничего). 3.К удалению назначаются помеченные объекты, у которых следующий объект не помечен: объект г удаляется, если он помечен, a next[i] не помечен (никаким другим процессором). Описанные действия выполняются за время 0(1) и не используют одновременный доступ к памяти. Очевидно, что требование 1 выполнено (каждый процессор выбирает не более одного элемента). Требование 2 также выполнено, так как объекты г и next[i] не могут быть выбраны одновременно - если next[i] выбран, то он должен быть помечен - а тогда объект г не выбирается. 30.4.3.Анализ Поскольку шаг рекурсии занимает время 0(1), необходимо оценить лишь количество шагов, после которого список станет пустым. Пусть на этапе 1 описанного процесса какой-то процессор выбрал объект г. Какова вероятность того, что объект г попадёт в |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||