Средства разработки приложений
Анализ существующих математических моделей вычислительных процессов в базовых блоках
Существует ряд моделей вычислительных процессов в базовых блоках. Наиболее распространенные из них используют для представления базового блока направленные ациклические графы [] , [], [].
Во всех распространенных графовых моделях базовых блоков множество вершин соответствует множеству команд, а наличие дуги между двумя вершинами соответствует наличию зависимости между соответствующими командами (дуга (v, u) показывает, что команда v должна быть выполнена раньше команды u).
Для того чтобы задать протяженность задержки между командами, в наиболее популярной модели, описанной в [] и [], используются числовые пометки ребер графа, соответствующие продолжительностям задержек - D((v, u)).
На Рис. 1 и 2 представлен пример содержимого базового блока и его традиционное представление с помощью графа. mov a, b add c, 1 mul a, c mov d, c mul a, d
Рис. 1.Пример содержимого базового блока
Рис. 2. Традиционное представление базового блока в виде графа
Корректным расписанием S для систем с одним конвейером называется функция S: (V→N│∀(v,u)∈E⇒S(u)-S(v)>D((v,u))). Таким образом, S(v) - позиция вершины v в результирующем расписании. В каждой позиции расписания может находиться либо одна инструкция, либо специальная команда NOP, которая не выполняет никаких действий. mov a, b add c, 1 mul a, c nop mov d, c mul a, d
Рис. 3. Пример корректного расписания для базового блока
Существует множество моделей, построенных на основе описанной выше, отличающихся различными атрибутами вершин и дуг, в зависимости от особенностей архитектуры целевых машин.
В некоторых распространенных архитектурах, например Intel i860 [], зависимости между командами могут быть ограничены по времени сверху. То есть вторая (зависящая) инструкция должна быть выполнена ровно через определенное количество тактов после первой, иначе результат выполнения первой команды будет утерян. Хотя такие виды зависимостей и описываются существующими моделями [], [], но эффективных алгоритмов построения расписания, создающих корректное расписание всегда, когда это возможно, для них не существует.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий