Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

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

Кроме того, в традиционных моделях базовых блоков не учитываются команды перехода, имеющие неустранимые задержки. Такие задержки допустимо заполнять полезными командами, если это не приводит к конфликтам по данным. Так как такое ограничение плохо вписывается в существующие модели, то для решения этой задачи используются специальные алгоритмы [3].

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

Разреженная модель вычислительных процессов в базовых блоках

Традиционная графовая модель базовых блоков использует в качестве узлов отдельные команды целевой машины, из которых состоит базовый блок [5]. Такая модель не отражает загруженности конвейера непроизводительными вычислениями и не позволяет оперировать командами, размер которых больше одного машинного слова.

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

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

Разреженную модель базовых блоков можно математически описать с помощью следующего ациклического графа:

G=(V; E; s; e), где

V - множество узлов, соответствующих конвейерным операциям, формирующим базовый блок

E⊂VxV - множество связей, определяющих порядок поступления узлов-операций (команд и задержек) на конвейер процессора

s∈V - стартовый (корневой) узел

e∈V - последний узел в любом корректном расписании, построенном на основе данного графа.

Узлы в таком графе должны быть помечены соответственно их назначению - являются ли они выборками кода команды из памяти, либо непроизводительными задержками.

Для решения поставленных задач необходимо ввести два вида связей между вершинами.

Введем следующие определения:

Определение 1: Связь называется "жесткой", если две операции, которые она соединяет должны поступать на конвейер строго друг за другом (между ними не должно быть других операций).

Обозначим подмножество жестких связей как H.

Определение 2: Связь называется "гибкой", если она задает лишь относительный порядок поступления операций на конвейер (между ними на конвейер могут поступать другие операции).

Множество задержек введено для моделирования минимального времени между инструкциями, которое традиционно [3] представляется в виде числовой пометки дуги. В предлагаемой модели паузы между инструкциями заполняются с помощью непроизводительных операций.

Рис. 4. Представление базового блока с помощью разреженной модели

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

В графе существует только одна корневая вершина - s.

В графе существует только один лист - e.

Граф является слабо связным.

Рекомендуем скачать другие рефераты по теме: решебник по математике виленкин, рефераты на украинском языке.



Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки