Cтраница 2
В тех случаях, когда нет строгого критерия, по которому может быть получен граф несовместимости ( например, изделия слабо коррелируются по типам входящих в них МС), применяются методы группирования, учитывающие каждый конструк-торско-технологический признак изделия в отдельности. [16]
Полученный график показывает ( рис 3.16), что экономия памяти, производимая раскраской графа несовместимости, может быть весьма существенной. [17]
Напомнив эти факты, мы заодно перечислили основные внутренние объекты, возникающие при построении графа несовместимости. Поскольку отношение несовместимости должно быть вычислено попарно для всех величин, правда, с учетом симметрии, нам перед вычислением матрицы U нужно иметь R и Т для всех Z величин. Поскольку каждое множество - эго шкала длины га, мы приходим к описанию этих множеств в виде матриц цел массив R, Т [: /, 1: га ], а также получаем естественное структурирование задачи. [18]
Содержательный анализ задачи подсказал нам, что эта задача решается в два этапа: построение графа несовместимости U и его раскраска. [19]
Итак, на основе сделанного небольшого открытия мы можем сформулировать нашу гипотезу так, что вершинами графа несовместимости являются компоненты связности информационного графа операторной схемы. Как таковые, они заслуживают особого термина. Так как содержательный анализ у нас позади, то смысл этого термина нам ясен: всем полюсам, входящим в область действия, сопоставляется одна и та же величина. [20]
В этой главе, оставаясь на уровне рассмотрения абстрактных объектов, мы постараемся попять, как все эти объекты могут бЕлть построены: как найти компоненты связности информационного графа, как определить множества R ( что просто) и Т ( что существенно сложнее), как, наконец, найти наилучшую раскраску графа несовместимости. Для этих построений нам нужно найти систематические процедуры, которые могут быть положены в основу практического решения задачи экономии памяти, например, на ЭВМ с помощью алгольных программ. [21]
Следующим этапом глобальной экономии является оптимальное определение совместимых переменных с обеспечением минимального расхода памяти. Вершины графа несовместимости означают переменные, а ребра соединяют две несовместимые по памяти переменные. [22]
Для оптимального группирования строится граф несовместимости, вершинам которого взаимно однозначно соответствуют изделия из ССЗ и две вершины смежны, если соответствующие им изделия не могут быть помещены в одну группу. Минимальная раскраска графа дает минимальное число групп, что минимизирует время переналадок ГПМ, необходимых при выпуске изделий из одной группы. [23]
Мы хотим прежде всего структурировать нашу программу выделением крупных разделов, которые образуют в свою очередь содержание параграфов данной главы. ЭКОНОМИЯ ПАМЯТИ естественно расчленяется на получение графа несовместимости и на его последующую раскраску, которая и задаст нужное распределение памяти. Аналогично графу переходов мы зададим граф несовместимости его матрицей смежности цел массив U [ i: I, 1: I ], в которой U [ i, / ] 1, если i-я и У-Я области несовместимы, и U [ i, j ] О в противном случае. Очевидно, что матрица U - симметрична. [24]
Правильная раскраска графа несовместимости в минимальное число цветов дает возможность самого экономного распределения памяти. Число использованных цветов дает минимальное необходимое для реализации схемы количество ячеек памяти; при этом всем вершинам графа несовместимости, окрашенным в один цвет, сопоставляется одна и та же величина. [25]
Мы хотим прежде всего структурировать нашу программу выделением крупных разделов, которые образуют в свою очередь содержание параграфов данной главы. ЭКОНОМИЯ ПАМЯТИ естественно расчленяется на получение графа несовместимости и на его последующую раскраску, которая и задаст нужное распределение памяти. Аналогично графу переходов мы зададим граф несовместимости его матрицей смежности цел массив U [ i: I, 1: I ], в которой U [ i, / ] 1, если i-я и У-Я области несовместимы, и U [ i, j ] О в противном случае. Очевидно, что матрица U - симметрична. [26]
Для системного программиста удобно считать, что в его распоряжении находится неограниченное число регистров, но, прежде чем осуществлять генерацию окончательного кода, необходимо отобразить это неограниченное множество виртуальных регистров на конечное множество регистров реальной машины. Первым шагом в распределении регистров является подготовка графа несовместимости. Каждый виртуальный регистр, так же как и реальный, представляется вершиной графа. Два виртуальных регистра, которые не могут сосуществовать / в одном реальном, называются несовместимыми; соответствующие вершины в графе несовместимости соединяются ребром. Затем отыскивается минимальная раскраска графа несовместимости. Если потребовавшееся число цветов не превышает числа реальных регистров, то распределение регистров осуществляется закреплением за каждым виртуальным регистром реального регистра того же цвета. [27]
Например, мы могли бы сильно сэкономить на времени построения графа несовместимости, задавая в качестве начального значения его компонент не нули, а результат перемножения множеств Rt на RJ, где Rt - множество начальных операторов i - й величины канонического оператора. [28]
Граф примера 10 таким свойством не обладает: в нем нет трех попарно смежных вершин, однако он требует трех красок. Мы уже, пожалуй, привыкли к тому, что мелкие отличия оказываются источником серьезных проблем. Так и сейчас: мы обязаны сказать себе, что раскраской вершин графа несовместимости как самостоятельной задачей нам надо будет в свое время серьезно заняться. [29]
Для системного программиста удобно считать, что в его распоряжении находится неограниченное число регистров, но, прежде чем осуществлять генерацию окончательного кода, необходимо отобразить это неограниченное множество виртуальных регистров на конечное множество регистров реальной машины. Первым шагом в распределении регистров является подготовка графа несовместимости. Каждый виртуальный регистр, так же как и реальный, представляется вершиной графа. Два виртуальных регистра, которые не могут сосуществовать / в одном реальном, называются несовместимыми; соответствующие вершины в графе несовместимости соединяются ребром. Затем отыскивается минимальная раскраска графа несовместимости. Если потребовавшееся число цветов не превышает числа реальных регистров, то распределение регистров осуществляется закреплением за каждым виртуальным регистром реального регистра того же цвета. [30]