Архитектура параллельных вычислительных систем

Упражнение 1:

Номер 1

ВС SPMD-архитектуры содержит 2 процессора. Составьте план выполнения монопрограммы логического вывода по базе знаний, содержащей массив {α} логических высказываний на базе системы аксиом {α}={α₀,α₁,b₂,b₃,c₄,c₅}. Система аксиом α₀→b₂,α₀→b₃,α₁→b₃,b₂→c₄,b₃→c₅

Ответ:

(1)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₂`			0
2	`α₀→b₃`			1
3	`α₁→b₃`			0
4	`α₀→b₂→с₄`	1	0	1
5	`α₀→b₃→с₅`	2	1	0
6	`α₁→b₃→с₅`	3	0	1

(2)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₂`			1
2	`α₀→b₃`			0
3	`α₁→b₃`			1
4	`α₀→b₂→с₄`	1	1	1
5	`α₀→b₃→с₅`	2	1	0
6	`α₁→b₃→с₅`	3	0	1

(3)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₂`			0
2	`α₀→b₃`			1
3	`α₁→b₃`			0
4	`α₀→b₂→с₄`	1	0	1
5	`α₁→b₃→с₅`	2	1	0
6	`α₀→b₃→с₅`	3	0	1

Номер 2

ВС SPMD-архитектуры содержит 2 процессора. Составьте план выполнения монопрограммы логического вывода по базе знаний, содержащей массив {α}логических высказываний на базе системы аксиом {α}={α₀,α₁,α₂,b₃,c₄,c₅}. Система аксиом α₀→c₄,α₁→b₃,α₂→b₄,b₃→c₅,b₄→c₆

Ответ:

(1)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→c₄`			0
2	`α₁→b₃`			1
3	`α₂→b₄`			0
4	`α₁→b₃→c₅`	2	1	1
5	`α₂→b₄→c₆`	3	0	0

(2)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→c₄`			0
2	`α₁→b₃`			1
3	`α₂→b₄`			0
4	`α₁→b₃→c₅`	2	0	1
5	`α₂→b₄→c₆`	3	1	0

(3)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→c₄`			0
2	`α₁→b₃`			1
3	`α₂→b₄`			0
4	`α₂→b₄→c₆`	2	1	1
5	`α₁→b₃→c₅`	3	0	0

Номер 3

ВС SPMD-архитектуры содержит 2 процессора. Составьте план выполнения монопрограммы логического вывода по базе знаний, содержащей массив {α} логических высказываний на базе системы аксиом {α}={α₀,α₁,α₂,b₃,b₄,b₅,c₆,c₇}. Система аксиом α₀→b₃,α₀→b₄,α₁→b₄,α₂→c₇,b₃→c₆,b₄→c₇

Ответ:

(1)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₃`			0
2	`α₀→b₄`			1
3	`α₁→b₄`			0
4	`α₂→c₇`			1
5	`α₀→b₃→c₆`	1	0	0
6	`α₀→b₄→c₇`	2	1	1
7	`α₁→b₄→c₇`	3	0	0

(2)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₃`			0
2	`α₀→b₄`			1
3	`α₁→b₄`			0
4	`α₂→c₇`			1
5	`α₀→b₃→c₆`	1	1	0
6	`α₀→b₄→c₇`	2	0	1
7	`α₁→b₄→c₇`	3	1	0

(3)

№	Логические цепочки	Продленная цепочка	Формирующий процессор	Обрабатывающий процессор
1	`α₀→b₃`			0
2	`α₀→b₄`			1
3	`α₁→b₄`			0
4	`α₂→c₇`			1
5	`α₀→b₄→c₇`	1	0	0
6	`α₀→b₃→c₆`	2	1	1
7	`α₁→b₄→c₇`	3	0	0

Упражнение 2:

Номер 1

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

Ответ:

(1) так легче использовать возможности системы команд

(2) малые элементарные объемы работ, выполняемых на одном шаге, способствуют равной загрузке процессоров

(3) таким способом эффективно реализуется ИЛИ-параллелизм (каждый процессор участвует в формировании нескольких логических цепочек) и И-параллелизм (несколько процессоров участвуют в формировании одной логической цепочки, по принципу конвейера). Это содействует полной и равной загрузке процессоров, что поддерживается системой команд

(4) закреплять за процессорами отдельные логические цепочки нецелесообразно из-за различной трудоемкости их обработки

Номер 2

Рассмотрите способы оптимизации загрузки процессоров, применение которых становится возможным в ВС SPMD-архитектуры с малыми накладными расходами на организацию параллельных вычислений. Зачем в базе знаний хранятся все промежуточные варианты построения логических цепочек?

Ответ:

(1) чтобы легче было определить многообразные варианты их последующего ветвления

(2) чтобы контролировать формирование дедуктивного ряда

(3) чтобы выделить минимальное число ординарных действий при обработке логических цепочек, невзирая на их ветвление (размножение), а, следовательно, - чтобы упростить монопрограмму

Номер 3

Рассмотрите способы оптимизации загрузки процессоров, применение которых становится возможным в ВС SPMD-архитектуры с малыми накладными расходами на организацию параллельных вычислений. Какие возможности для оптимизации загрузки процессоров предоставляют дескрипторы массивов

Ответ:

(1) они являются основным средством взаимодействия с элементами массивов, их контроля и преобразования. Это основной механизм представления данных, на который ориентирована система команд

(2) они минимизируют затраты времени на организацию переадресации процессоров и данных, индексации, базирования, проверки выхода за границы массива и других видов адресации данных

(3) дескрипторы массивов способствуют переадресации процессоров для выборки закрепленных за ними элементов массива

(4) дескрипторы массивов хранят и модифицируют шаги переадресации

Упражнение 4:

Номер 1

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

Ответ:

(1) локальные данные процедур, выполняющихся параллельно

(2) глобальные данные, дескрипторы массивов, примитивы синхронизации, изменяемые одними процессорами без своевременного оповещения других

(3) адресная информация, изменение которой не согласовано процессорами

Номер 2

Рассмотрите проблемы когерентности кэшей. Какие способы обеспечения когерентности кэшей следует считать эффективными?

Ответ:

(1) периодический обмен кэшами по общей шине

(2) снабжение каждого "глобала" значением времени последнего изменения при обновлении состояния кэша процессора в памяти других процессоров

(3) cинхронизация изменения "глобалов", закрытых другими процессорами с помощью механизма закрытия адресов (в ВС SPMD-архитектуры). Списки закрытых адресов доступны каждому процессору

(4) периодический "сброс" всех кэшей для их естественного заполнения вновь из ОП

(5) функциональное разбиение кэша на области хранения разных типов данных с разными процедурами, обеспечивающими когерентность

Номер 3

Рассмотрите проблемы когерентности кэшей. Как реализуется когерентность кэшей на основе принципа data flow?

Ответ:

(1) с помощью обмена таблицами закрытых адресов, использующими списки закрытых виртуальных адресов решаемых задач. Закрытый адрес свидетельствует о неготовности информации

(2) с помощью комплексного алгоритмического анализа необходимости поддержки когерентности кэшей

(3) периодическим обменом состояния кэшей по общей шине

Номер 4

Рассмотрите проблемы когерентности кэшей. Как механизм закрытия адресов влияет на механизм когерентности кэшей?

Ответ:

(1) с помощью соблюдения "культуры" использования "глобалов" - закрытия их адресов до окончания формирования значений и их записи по этим адресам, а также с помощью оперативного обмена списками закрытых адресов

(2) c помощью оперативного обмена текущим состоянием всех кэшей

(3) c помощью сравнения времени формирования данных

Упражнение 6:

Номер 1

Рассмотрите возможные средства синхронизации параллельных вычислений в ВС SPMD-архитектуры. Как реализуется механизм закрытия адресов?

Ответ:

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

(2) по закрытому адресу запрещается запись, но разрешается считывание. Запись любого процессора по этому адресу открывает его

(3) по закрытому адресу запрещается считывание, пока какой-либо процессор не произведет запись

Номер 2

Рассмотрите возможные средства синхронизации параллельных вычислений в ВС SPMD-архитектуры. Как реализуется механизм предикатов?

Ответ:

(1) любой процессор может сформировать значение булевой переменной – предиката в общей памяти предикатов. В зависимости от значения предиката, поставленного в соответствие команде, эта команда выполняется в спекулятивном режиме

(2) значения предикатов используются для организации условных переходов

(3) предикаты используются для организации режима data flow

Номер 3

Рассмотрите возможные средства синхронизации параллельных вычислений в ВС SPMD-архитектуры. Применение механизмов синхронизации, в свою очередь, должно также быть синхронным. Какие механизмы синхронизации выполнения программ используются в ВС SPMD-архитектуры?

Ответ:

(1) команда СИНХ заставляет все копии монопрограммы одновременно начать или продолжить выполнение с общей точки

(2) синхронно начать или продолжить выполнение копий монопрограммы можно с помощью команды "закрыть адрес"

(3) синхронизация во времени выполняется с помощью таймера

(4) синхронизация во времени выполняется с помощью механизма предикатов

Архитектура параллельных вычислительных систем - тест 13