Танненбаум Е. Архітектура компютера [pdf]
.pdf
Вопросы и задания |
5 |
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, Eugen Madison, New Haven, Palo Alto, Pasadena, Santa Cruz, Stony Brook, Westwoo Yellow Springs. Когда будете вычислять средний элемент в списке из четн го числа элементов, возьмите элемент, который идет сразу после средне индекса.
12.Можно ли использовать двоичный поиск в таблице, в которой содержит
простое число элементов?
5 5 4 Глава 7. Уровень языка ассемблера
Образует ли каждое символьное имя уникальное значение хэш-фун Если нет, то как можно разрешить эту коллизию?
14.Метод хэш-кодирования, описанный в тексте, связывает все элементы ющие один хэш-код, в связном списке. Альтернативный метод — имет ко одну таблицу из п слотов, в которой в каждом слоте имеется про ство для одного ключа и его значения (или для указателей на них) алгоритм хэшированияпорождаетслот, которыйужезаполнен, произв вторая попытка с использованием того же алгоритма хэширования. на этот раз слот заполнен, алгоритм используется снова и т. д. Так п жается до тех пор, пока не будет найден пустой слот. Если доля слотов рые уже заполнены, составляет R, сколько попыток в среднем понад для того, чтобы ввести в таблицу новый символ?
15.Вероятно, когда-нибудь в будущем на одну микросхему можно будет щать тысячи идентичных процессоров, каждый из которых содержит не ко слов локальной памяти. Если все процессоры могут считывать и за вать три общих регистра, то как можно реализовать ассоциативную п
16.Pentium II имеет сегментированную архитектуру. Сегменты незави Ассемблер для этой машины может содержать директиву SEG N, котор мещает последующий код и данные в сегмент N. Повлияет ли такая сх счетчик адреса команды?
17.Программы часто связаны с многочисленными файлами DLL (дина ки подсоединяемыми библиотеками). А не будет ли более эффект просто поместить все процедуры в один большой файл DLL, а затем у вить связь с ним?
18.Можно ли отобразить файл DLL в виртуальные адресные пространст процессов с разными виртуальными адресами? Если да, то какие про при этом возникают? Можно ли их разрешить? Если нет, то что мож лать, чтобы устранить их?
19.Опишем один из способов связывания. Перед сканированием библи компоновщик составляет список необходимых процедур, то есть име торые в связываемых модулях определены как внешние (EXTERN). компоновщик последовательно просматривает всю библиотеку, из каждую процедуру, которая находится в списке нужных имен. Будет ботать такая схема? Если нет, то почему, и как это можно исправить?
20.Может ли регистр использоваться в качестве фактического параметра ровызове? А константа? Если да, то почему. Если нет, то почему.
21.Вам нужно реализовать макроассемблер. Из эстетических соображени начальник решил, что макроопределения не должны предшествовать вам макросов. Как повлияет это решение на реализацию?
Вопросы и задания
24.Напишите модуль таблицы символов, состоящий из двух процедур: enterisym value) и lookup(symbol, value). Первый вводит новые символьные имена в т лицу, а второй ищет их в таблице. Используйте какую-либо хэш-кодиро
25.Напишите простой ассемблер для компьютера Mic-1, о котором мы гово ли в главе 4. Помимо оперирования машинными командами обеспечьте в можность приписывать константы символьным именам во время ассемб рования, а также способ ассемблировать константу в машинное слово.
26.Добавьте макросы к ассемблеру, который вы должны были написать, полняя предыдущее задание.
Глава 8
Архитектуры компьютеров параллельного действия
Скорость работы компьютеров становится все выше, но и требования, пред емые к ним, тоже постоянно растут. Астрономы хотят воспроизвести всю и Вселенной с момента большого взрыва до самого конца. Фармацевты хот разрабатывать новые лекарственные препараты для конкретных заболевани мощью компьютеров, не принося в жертву целые легионы крыс. Разработч тательных аппаратов могли бы прийти к более эффективным результата бы всю работу за них выполняли компьютеры, и тогда им не нужно было б струировать аэродинамическую трубу. Если говорить коротко, насколько б ными ни были компьютеры, этого никогда не хватает для решения многи (особенно научных, технических и промышленных).
Скорость работы тактовых генераторов постоянно повышается, но ск коммутации нельзя увеличивать бесконечно. Главной проблемой остается с света, и заставить протоны и электроны перемещаться быстрее невозможно высокой теплоотдачи компьютеры превратились в кондиционеры. Након скольку размеры транзисторов постоянно уменьшаются, в какой-то моме мени каждый транзистор будет состоять из нескольких атомов, поэтому ос проблемой могут стать законы квантовой механики (например, гейзенберг принципнеопределенности).
Чтобы решать более сложные задачи, разработчики обращаются к компь параллельного действия. Невозможно построить компьютер с одним проце и временем цикла в 0,001 не, но зато можно построить компьютер с 1000 пр рами, время цикла каждого из которых составляет 1 не. И хотя во втором мы используем процессоры, которые работают с более низкой скоростью, производительность теоретически должна быть такой же.
Параллелизм можно вводить на разных уровнях. На уровне команд, нап можно использовать конвейеры и суперскалярную архитектуру, что поз увеличивать производительность примерно в 10 раз. Чтобы увеличить про тельность в 100, 1000 или 1 000 000 раз, нужно продублировать процессор
крайней мере, какие-либо его части и заставить все эти процессоры работать
Вопросы разработки компьютеров параллельного действия |
|
55 |
разработках используется небольшое число очень мощных элементов, а в других огромное число элементов со слабой мощностью. Существуют промежуточны типы компьютеров. В области параллельной архитектуры проведена огромная р бота. Мы кратко расскажем об этом в данной главе. Дополнительную информ цию можно найти в книгах [86,115, 131, 159].
Вопросы разработки компьютеров параллельного действия
Когда мы сталкиваемся с новой компьютерной системой параллельного действи возникает три вопроса:
1.Каков тип, размер и количество процессорных элементов?
2.Каков тип, размер и количество модулей памяти?
3.Как взаимодействуют элементы памяти и процессорные элементы?
Рассмотрим каждый из этих пунктов. Процессорные элементы могут быть с мых различных типов — от минимальных АЛУ до полных центральных процессо ров, а по размеру один элемент может быть от небольшой части микросхемы д кубического метра электроники. Очевидно, что если процессорный элемент пре ставляет собой часть микросхемы, то можно поместить в компьютер огромное числ таких элементов (например, миллион). Если процессорный элемент представляе собой целый компьютер со своей памятью и устройствами ввода-вывода, цифр будут меньше, хотя были сконструированы такие системы даже с 10 000 процессо рами. Сейчас компьютеры параллельного действия конструируются из серийн выпускаемых частей. Разработка компьютеров параллельного действия часто за висит от того, какие функции выполняют эти части и каковы ограничения.
Системы памяти часто разделены на модули, которые работают независимо др от друга, чтобы несколько процессоров одновременно могли осуществлять досту к памяти. Эти модули могут быть маленького размера (несколько килобайтов) ил большого размера (несколько мегабайтов). Они могут находиться или рядом с про цессорами, или на другой плате. Динамическая память (динамическое ОЗУ) рабо тает гораздо медленнее центральных процессоров, поэтому для повышения скоро сти доступа к памяти обычно используются различные схемы кэш-памяти. Може быть два, три и даже четыре уровня кэш-памяти.
Хотя существуют самые разнообразные процессоры и системы памяти, систе мы параллельного действия различаются в основном тем, как соединены разны части. Схемы взаимодействия можно разделить на две категории: статически и динамические. В статических схемах компоненты просто связываются друг с др гом определенным образом. В качестве примеров статических схем можно приве сти звезду, кольцо и решетку. В динамических схемах все компоненты подсоеди
5 5 8 Глава 8. Архитектуры компьютеров параллельного действия
параллельно. Здесь существует несколько вариантов. Некоторые компьюте раллельного действия одновременно выполняют несколько независимых зада задачи никак не связаны друг с другом и не взаимодействуют. Типичный при компьютер, содержащий от 8 до 64 процессоров, представляющий собой бо систему UNIX с разделением времени, с которой могут работать тысячи пол телей. В эту категорию попадают системы обработки транзакций, котор пользуются в банках (например, банковские автоматы), на авиалиниях (н мер, системы резервирования) и в больших web-серверах. Сюда же отн независимые прогоны моделирующих программ, при которых использует сколько наборов параметров.
Другие компьютеры параллельного действия выполняют одну задачу, с щую из нескольких параллельных процессов. В качестве примера рассмотри грамму игры в шахматы, которая анализирует данные позиции на доске, по ет список возможных из этих позиций ходов, а затем порождает паралле процессы, чтобы проанализировать каждую новую ситуацию параллельно. параллелизм нужен не для того, чтобы обслуживать большое количество п вателей, а чтобы ускорить решение одной задачи.
Далее идут машины с высокой степенью конвейеризации или с большим чеством АЛУ, которые обрабатывают одновременно один поток команд. В тегорию попадают суперкомпьютеры со специальным аппаратным обеспеч для обработки векторных данных. Здесь решается одна главная задача, и пр все части компьютера работают вместе над одним аспектом этой задачи (н мер, разные элементы двух векторов суммируются параллельно).
Этитри примераразличаются по так называемой степенидетализации. гопроцессорных системах с разделением времени блок параллелизма дост велик — целая пользовательская программа. Параллельная работа больших программного обеспечения практически без взаимодействия между этими ми называется параллелизмом на уровне крупных структурных единиц. Д рально противоположный случай (при обработке векторных данных) назы
параллелизмом на уровне мелких структурных единиц.
Термин «степень детализации» применяется по отношению к алгоритмам граммному обеспечению, но у него есть прямой аналог в аппаратном обеспе Системы с небольшим числом больших процессоров, которые взаимодей по схемам с низкой скоростью передачи данных, называются системами с к ной(слабой)связью.Импротивопоставляютсясистемыснепосредственно ной) связью, в которых компоненты обычно меньше по размеру, распол ближе друг к другу и взаимодействуют через специальные коммуникационны с высокой пропускной способностью. В большинстве случаев задачи с па лизмом на уровне крупных структурных единиц лучше всего решаются в си со слабой связью, а задачи с параллелизмом на уровне мелких структурны
Вопросы разработки компьютеров параллельного действия
В следующих разделах мы рассмотрим некоторые вопросы разработки ком теров параллельного действия. Мы начнем с информационных моделей и с межсоединений, затем рассмотрим вопросы, связанные с производительност программным обеспечением, и, наконец, перейдем к классификации архите компьютеров параллельного действия.
Информационные модели
В любой системе параллельной обработки процессоры, выполняющие разные ти одной задачи, должны как-то взаимодействовать друг с другом, чтобы обм ваться информацией. Как именно должен происходить этот обмен? Было пре жено и реализовано две разработки: мультипроцессоры и мультикомпьютеры рассмотрим их ниже.
Мультипроцессоры
В первой разработке все процессоры разделяют общую физическую память показано на рис. 8.1, а. Такая система называется мультипроцессором или с
мой с совместно используемой памятью.
Мультипроцессорная модель распространяется на программное обеспеч Все процессы, работающие вместе на мультипроцессоре, могут разделять одно туальное адресное пространство, отображенное в общую память. Любой про может считывать слово из памяти или записывать слово в память с помощью манд LOAD и STORE. Больше ничего не требуется. Два процесса могут обменив информацией, если один из них будет просто записывать данные в память, а гой будет считывать эти данные.
р |
р |
р |
р |
•Процессор |
р |
р |
р |
р |
I I |
I |
|
~ |
|
|
|
|
|
Память
совместного
использования
1 1 1 1
р р р р
Рис. 8 . 1 . Мультипроцессор, содержащий 16 процессоров, которые разделяют общу память (а); изображение, разбитое на 16 секций, каждую из которых анализирует отдельный процессор (б)
Вопросы разработки компьютеров параллельного действия |
|
561 |
При отсутствии памяти совместного использования в аппаратном обеспечении предполагается определенная структура программного обеспечения. В мультикомпьютере невозможно иметь одно виртуальное адресное пространство, из которого все процессы могут считывать информацию и в которое все процессы могут записыватьинформациюпростопутемвыполнениякомандLOADиSTORE.Например,если процессор 0 (в верхнемлевом углу) нарис. 8.1, ^обнаруживает, что часть его объекта попадает в другую секцию, относящуюся к процессору 1, он может продолжать считывать информацию из памяти, чтобы получить хвост самолета. Однако если процессор 0 на рис. 8.2, # обнаруживает это, он не может просто считать информацию из памяти процессора 1. Для получения необходимых данных ему нужно сделать что-то другое.
Вчастности, ему нужно как-то определить, какой процессор содержит необходимые ему данные, и послать этому процессору сообщение с запросом копии данных. Затем процессор 0 блокируется до получения ответа. Когда процессор 1 получает сообщение, программное обеспечение должно проанализировать его и отправить назад необходимые данные. Когда процессор 0 получает ответное сообщение, программное обеспечение разблокируется и продолжает работу.
Вмультикомпьютере для взаимодействия между процессорами часто используются примитивы send и receive. Поэтому программное обеспечение мультикомпьютера имеет более сложную структуру, чем программное обеспечение мультипроцессора. При этом основной проблемой становится правильное разделение данных и разумное их размещение. В мультипроцессоре размещение частей не влияет на правильность выполнения задачи, хотя может повлиять на производительность. Таким образом, мультикомпьютер программировать гораздо сложнее, чем мультипроцессор.
Возникает вопрос: зачем вообще создавать мультикомпыотеры, если мультипроцессоры гораздо проще запрограммировать? Ответ прост: гораздо проще и дешевле построить большой мультикомпьютер, чем мультипроцессор с таким же количеством процессоров. Реализация общей памяти, разделяемой несколькими сотнями процессоров, — это весьма сложная задача, а построить мультикомпьютер, содержащий 10 000 процессоров и более, довольно легко.
Таким образом, мы сталкиваемся с дилеммой: мультипроцессоры сложно строить, но легко программировать, а мультикомпыотеры легко строить, но трудно программировать. Поэтому стали предприниматься попытки создания гибридных систем, которые относительно легко конструировать и относительнолегко программировать. Это привело к осознанию того, что совместную память можно реализовывать по-разному, и в каждом случае будут какие-то преимущества и недостатки. Практически все исследования в области архитектур с параллельной обработкой направлены на создание гибридных форм, которые сочетают в себе преимуще-
5 6 2 Глава 8. Архитектуры компьютеров параллельного действия
память на любом из нескольких уровней, как показано на рис. 8.3. На рис мы видим память совместного использования, реализованную в аппаратно печении в виде реального мультипроцессора. В данной разработке имеетс копия операционной системы с одним набором таблиц, в частности таблиц пределения памяти. Если процессу требуется больше памяти, он прерывае ту операционной системы, которая после этого начинает искать в таблице с ную страницу и отображает эту страницу в адресное пространство вызыв программы. Что касается операционной системы, имеется единая память, и ционная система следит, какая страница в программном обеспечении при жит тому или иному процессу. Существует множество способов реализац вместной памяти в аппаратном обеспечении.
Второй подход — использовать аппаратное обеспечение мультикомпью операционную систему, которая моделирует разделенную память, обесп единое виртуальное адресное пространство, разбитое на страницы. При тако ходе, который называется DSM (Distributed Shared Memory — распреде совместно используемая память) [82,83, 84], каждая страница расположен ном из блоков памяти (см. рис. 8.2, с). Каждая машина содержит свою соб ную виртуальную память и собственные таблицы страниц. Если процесс вершает команду LOAD или STORE над страницей, которой у него нет, прои прерывание операционной системы. Затем операционная система находи ную страницу и требует, чтобы процессор, который обладает нужной стра преобразовал ее в исходную форму и послал по сети межсоединений. Когд ница достигает пункта назначения, она отображается в память, и выполнен рванной команды возобновляется. По существу, операционная система вызывает недостающие страницы не с диска, а из памяти. Но у пользоват здается впечатление, что машина содержит общую разделенную память. D рассмотрим ниже в этой главе.
Третий подход — реализовать общую разделенную память на уровне про ного обеспечения. При таком подходе абстракцию разделенной памяти создае программирования, и эта абстракция реализуется компилятором. Наприм дель Linda основана на абстракции разделенного пространства кортежей (з данных, содержащих наборы полей). Процессы любой машины могут взя теж из общего пространства или отправить его в общее пространство. Пос доступ к этому пространству полностью контролируется программным обе нием (системой Linda), никакого специального аппаратного обеспечения и циальной операционной системы не требуется.
Другой пример памяти совместного использования, реализованной в про ном обеспечении, — модель общих объектов в системе Огса. В модели Огса п сы разделяют объекты, а не кортежи, и могут выполнять над ними те ил
процедуры. Если процедура изменяет внутреннее состояние объекта, опер
