Файл: Tannenbaum.pdf

Вопросы и задания 553

3. Придумайте, как программисты на языке ассемблера могут определять си-

нонимы для кодов операций. Как это можно реализовать?

4. Все ассемблеры для процессоров Intel имеют в качестве первого операнда

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

5. Можно ли следующую программу ассемблировать в два прохода?

 Примеча-

ние:

 EQU — это директива, которая приравнивает метку и выражение в поле

операнда.

A EQU В

В EQU С
С EQU D
О EQU 4

6. Одна компания планирует разработать ассемблер для компьютера с 40-бит-

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

хранить в одном слове. Скрудж объявил, что символьные имена могут со-
стоять только из букв, причем буква Q запрещена. Какова максимальная
длина символьного имени? Опишите вашу схему кодировки.

7. Чем отличается команда от директивы?
8. Чем отличается счетчик адреса команд от счетчика команд? А существует

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

9. Какой будет таблица символов (имен) после обработки следующих опера-

торов ассемблера для Pentium II (первому оператору приписан адрес 1000)?

EVEREST: POP BX (1 байт)

К2: PUSH BP (1 байт)

WHITNEY: MOV BP.SP (2 байта)

MCKINLEY: PUSH X (3 байта)

FUJI: PUSH SI (1 байт)

KIBO: SUB SI.300 (3 байта)

10. Можете ли вы представить себе обстоятельства, при которых метка совпа-

дет с кодом операции (например, может ли быть MOV меткой)? Аргументи-
руйте.

11. Какие шаги нужно совершить, чтобы, используя двоичный поиск, найти эле-

мент «Berkeley» в следующем списке: Ann Arbor, Berkeley, Cambridge, Eugene,

Madison, New Haven, Palo Alto, Pasadena, Santa Cruz, Stony Brook, Westwood,

Yellow Springs. Когда будете вычислять средний элемент в списке из четно-
го числа элементов, возьмите элемент, который идет сразу после среднего
индекса.

12. Можно ли использовать двоичный поиск в таблице, в которой содержится

простое число элементов?

13. Вычислите хэш-код для каждого из следующих символьных имен. Для это-

го сложите буквы (А=1, В=2 и т. д.) и возьмите результат по модулю разме-
ра хэш-таблицы. Хэш-таблица содержит 19 слотов (от 0 до 18).
els, jan, jelle, maaike

5 5 4 Глава 7. Уровень языка ассемблера

Образует ли каждое символьное имя уникальное значение хэш-функции?
Если нет, то как можно разрешить эту коллизию?

14. Метод хэш-кодирования, описанный в тексте, связывает все элементы, име-

ющие один хэш-код, в связном списке. Альтернативный метод — иметь толь-
ко одну таблицу из п слотов, в которой в каждом слоте имеется простран-
ство для одного ключа и его значения (или для указателей на них). Если
алгоритм хэширования порождает слот, который уже заполнен, производится
вторая попытка с использованием того же алгоритма хэширования. Если и
на этот раз слот заполнен, алгоритм используется снова и т. д. Так продол-
жается до тех пор, пока не будет найден пустой слот. Если доля слотов, кото-
рые уже заполнены, составляет R, сколько попыток в среднем понадобится
для того, чтобы ввести в таблицу новый символ?

15. Вероятно, когда-нибудь в будущем на одну микросхему можно будет поме-

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

16. Pentium II имеет сегментированную архитектуру. Сегменты независимы.

Ассемблер для этой машины может содержать директиву SEG N, которая по-
мещает последующий код и данные в сегмент N. Повлияет ли такая схема на

счетчик адреса команды?

17. Программы часто связаны с многочисленными файлами DLL (динамичес-

ки подсоединяемыми библиотеками). А не будет ли более эффективным
просто поместить все процедуры в один большой файл DLL, а затем устано-
вить связь с ним?

18. Можно ли отобразить файл DLL в виртуальные адресные пространства двух

процессов с разными виртуальными адресами? Если да, то какие проблемы
при этом возникают? Можно ли их разрешить? Если нет, то что можно сде-
лать, чтобы устранить их?

19. Опишем один из способов связывания. Перед сканированием библиотеки

компоновщик составляет список необходимых процедур, то есть имен, ко-
торые в связываемых модулях определены как внешние (EXTERN). Затем
компоновщик последовательно просматривает всю библиотеку, извлекая
каждую процедуру, которая находится в списке нужных имен. Будет ли ра-
ботать такая схема? Если нет, то почему, и как это можно исправить?

20. Может ли регистр использоваться в качестве фактического параметра в мак-

ровызове? А константа? Если да, то почему. Если нет, то почему.

21. Вам нужно реализовать макроассемблер. Из эстетических соображений ваш

начальник решил, что макроопределения не должны предшествовать вызо-
вам макросов. Как повлияет это решение на реализацию?

22. Подумайте, как можно поместить макроассемблер в бесконечный цикл.
23. Компоновщик считывает 5 модулей, длины которых составляют 200, 800,

600, 500 и 700 слов соответственно. Если они загружаются в этом порядке,

то каковы константы перемещения?

Вопросы и задания 555

24. Напишите модуль таблицы символов, состоящий из двух процедур:

 enterisymbol,

value)

 и

 lookup(symbol, value).

 Первый вводит новые символьные имена в таб-

лицу, а второй ищет их в таблице. Используйте какую-либо хэш-кодировку.

25. Напишите простой ассемблер для компьютера Mic-1, о котором мы говори-

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

26. Добавьте макросы к ассемблеру, который вы должны были написать, вы-

полняя предыдущее задание.

Глава 8

Архитектуры компьютеров

параллельного действия

Скорость работы компьютеров становится все выше, но и требования, предъявля-
емые к ним, тоже постоянно растут. Астрономы хотят воспроизвести всю историю
Вселенной с момента большого взрыва до самого конца. Фармацевты хотели бы

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

Скорость работы тактовых генераторов постоянно повышается, но скорость

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

Чтобы решать более сложные задачи, разработчики обращаются к компьютерам

параллельного действия. Невозможно построить компьютер с одним процессором
и временем цикла в 0,001 не, но зато можно построить компьютер с 1000 процессо-

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

Параллелизм можно вводить на разных уровнях. На уровне команд, например,

можно использовать конвейеры и суперскалярную архитектуру, что позволяет
увеличивать производительность примерно в 10 раз. Чтобы увеличить производи-
тельность в 100, 1000 или 1 000 000 раз, нужно продублировать процессор или, по
крайней мере, какие-либо его части и заставить все эти процессоры работать вместе.

В этой главе мы изложим основные принципы разработки компьютеров парал-

лельного действия и рассмотрим различные примеры. Все эти машины состоят из

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

Вопросы разработки компьютеров параллельного действия 557

разработках используется небольшое число очень мощных элементов, а в других —
огромное число элементов со слабой мощностью. Существуют промежуточные
типы компьютеров. В области параллельной архитектуры проведена огромная ра-
бота. Мы кратко расскажем об этом в данной главе. Дополнительную информа-
цию можно найти в книгах [86,115, 131, 159].

Вопросы разработки компьютеров

параллельного действия

Когда мы сталкиваемся с новой компьютерной системой параллельного действия,
возникает три вопроса:

1. Каков тип, размер и количество процессорных элементов?

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

мых различных типов — от минимальных АЛУ до полных центральных процессо-
ров, а по размеру один элемент может быть от небольшой части микросхемы до
кубического метра электроники. Очевидно, что если процессорный элемент пред-
ставляет собой часть микросхемы, то можно поместить в компьютер огромное число
таких элементов (например, миллион). Если процессорный элемент представляет
собой целый компьютер со своей памятью и устройствами ввода-вывода, цифры

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

Системы памяти часто разделены на модули, которые работают независимо друг

от друга, чтобы несколько процессоров одновременно могли осуществлять доступ
к памяти. Эти модули могут быть маленького размера (несколько килобайтов) или
большого размера (несколько мегабайтов). Они могут находиться или рядом с про-
цессорами, или на другой плате. Динамическая память (динамическое ОЗУ) рабо-
тает гораздо медленнее центральных процессоров, поэтому для повышения скоро-
сти доступа к памяти обычно используются различные схемы кэш-памяти. Может
быть два, три и даже четыре уровня кэш-памяти.

Хотя существуют самые разнообразные процессоры и системы памяти, систе-

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

Компьютеры параллельного действия можно рассматривать как набор микро-

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