ЗАДАНИЯ. Рассмотрим таблицу распределения конвейера на рис.8

1. Конвейеризация

Рассмотрим таблицу распределения конвейера на рис.8. Предположим, что процессор располагает логикой продвижения, которая способна сказать, что команда A записывает в тот же регистр, из которого читает команда B и, следовательно, результат, записанный командой A, может быть прямо продвинут в АЛУ не дожидаясь завершения записи. Предположим, что логика продвижения не тратит времени.

Дать исправленную таблицу распределения. Сколько циклов потеряют пузыри?

2. Иерархия памяти

1. Рассмотрим функцию compute_variance для вычисления дисперсии целых чисел из массива data.

Предположим, что программа выполняется на 32-разрядном процессоре с кэш прямого отображения с параметрами (m; S; E; B) = (32; 8; 1; 8). Сделаем следующие допущения:

• целое представляется 4 байтами;

• sum1, sum2, result, и I сохраняются в регистрах;

• data сохраняется в памяти, начиная с адреса 0x0;

Необходимо ответить на следующие вопросы:

1) Рассмотрим случай, когда N = 16. Сколько промахов кэш будет в этом случае?

2) Предположим N = 32. Вычислить новое значение числа промахов.

3) Рассмотрим выполнение для N = 16 и 2-входовой кэш с параметрами

(m; S; E; B) = (32; 8; 2; 4). Сколько промахов кэш будет в этом случае?

2. Кэш использует среднюю часть бит адреса как множество индексов, а старшую как тэг. Почему так сделано? Как изменится производительность кэш, если средние биты использовать как тэг, а старшие как индекс?

3. Рассмотрим программу на Си и упрощенное отображение памяти 16-разрядного микроконтроллера как показано на рисунке.

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

Можно допустить, что в этой системе целые являются 16-битными, нет операционной системы, защиты памяти и что программа была откомпилирована и загружена в область C памяти.

1) Для каждой переменной n, m, и a показать, где в памяти (A, B, C, или D) переменные будут сохраняться.

2) Определить, что будет делать программа, если содержимое адреса 0x0010 при старте равно 0.

3) Определить, что будет делать программа, если содержимое адреса 0x0010 при старте равно 1.

3. Базовые устройства ввода-вывода встроенных систем

1. Предположим, что 4-х разрядный ADC-преобразователь работает по принципу последовательных приближений. Диапазон входного сигнала от V_min=1 В (=0000) до V_max=4.75 В (=1111). Какое количество шагов используется для преобразования значений 2.25 В, 3.75 В, and 1.8 В? Изобразить временную диаграмму преобразования этих значений.

4. Язык проектирования аппаратуры VHDL

1. Пусть дана реализация шины как на рисунке.

Какое значение из множества IEEE 1164 std_logic для VHDL будет на шине (bus), если оба разрешающих входа установить в ’0’ (ena 1 = ena 2 = ’0’)?

Какое значение из множества IEEE 1164 std_logic для VHDL будет на шине (bus), если ena 1 = ’0’, ena 2 = ’1’ and f 2 = ’1’?

5. Многозадачность

1. Дать EFSM-модель функции addListener на рис.73 подобно модели на рис. 74.

2. Допустим, что две целые глобальные переменные a и b разделяются несколькими потоками. Допустим, что lock_a и lock_b два замка мутекса, которые защищают доступ к a и b. Допустим, нельзя предположить, что чтение и запись целых глобальных переменных являются атомарными. Рассмотрим следующий код:

Допустим, для исключения взаимоблокировки команда разработчиков договорилась, что замок b должен быть всегда взят перед замком a любым кодом, берущим оба замка. Кроме того из-за производительности команда настаивает, что не надо излишне брать замок. Следовательно, неприемлемо модифицировать proc1 следующим образом:

Поток, вызывающий proc1 берет замок b излишне, когда a не равно arg.

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

Дать решение для proc1, которое минимизирует излишнее взятие замка b.

3. Реализация функции get на рис.78 допускает более одного вызывающего get потока. Однако, если изменить код в строках 30-32 для pthread_cond_wait на

тогда этот код будет работать, только если удовлетворяются два условия:

– pthread_cond_wait возвращается, только если есть соответствующий вызов pthread_cond_signal и

– есть только один поток-потребитель.

Пояснить, почему требуется второе условие.

4. Шаблон producer/consumer, реализованный на рис.77 имеет недостаток в том, что размер очереди используемой для буферизации сообщений неограничен. Программа может отказать в работе, исчерпав всю доступную память (отказ функции malloc). Написать вариант функций send и get, который ограничивает размер буфера до 5 сообщений.

5. Альтернативная форма передачи сообщений, называемая рандеву подобна шаблону producer/consumer на рис.77, но это синхронная процедура тесно связанная с потребителем. В частности на рис. 77 функция send возвращается немедленно независимо от того готов ли некоторый поток принять сообщение. При коммуникации в стиле рандеву процедура send не должна возвращаться пока процесс потребителя не достигнет соответствующего вызова get. Соответственно нет необходимости в буферизации сообщений.

Написать реализацию send и get для рандеву.

6. Валидация и оценка проекта

1. Представим состояние кэш в случае сходящегося потока управления. На рис. Показано состояние строки 4-входовой кэш в точке схождения для каждого из двух путей.

Что получится в результате анализа необходимости и возможности состояния кэш?

2. Рассмотрим пульсирующий поток событий. Поток периодический с периодом p. В начале каждого периода два события поступают с интервалом в d единиц времени. Построить кривые поступления для этого потока на интервале от 0 до 3 *p.

3. Представим, что обработкой потока занимается процессор с максимальной производительностью b.

а) На что похожи кривые обслуживания, если производительность ухудшится до величины b’ из-за конфликтов в кэш?

б) Как изменятся кривые обслуживания, если некоторый таймер будет прерывать задачи каждые 100 ms и если обслуживание прерывания выполняется 10 ms? Предполагается, что нет конфликтов в кэш.

в) На что похожи кривые обслуживания, если рассматривать конфликты в кэш как в а) и прерывания как в б)?

Результирующие кривые должны быть построены на интервале от 0 до 300 ms.