 |
модулей в монтажном пространстве
|
|
|
|
к выполнению лабораторной работы
по дисциплине "Основы конструирования ЭВМ"
Севастополь
УДК 681.3
Решение задачи размещения одногабаритных модулей в монтажном пространстве Методические указания к выполнению лабораторной работы по дисциплине «Основы конструирования ЭВМ». / Сост. Е.А. Кожаев, Л.В. Иванова. – Севастополь: Изд-во СевНТУ, 2004- 9 с.
Методические указания предназначены для изучения и использования методики решения задачи размещения одногабаритных модулей в монтажном пространстве (стадия непосредственно размещения) с оптимизацией решения по критерию минимума суммарной длины сигнальных связей между модулями
Методические указания предназначены для студентов специальности 7.091501 «Компьютерные системы и сети» дневной и заочной форм обучения.
Методические указания рассмотрены и утверждены на заседании кафедры кибернетики и вычислительной техники (протокол № 3 от 10.11.03г.).
Допущено учебно-методическим советом СевНТУ в качестве методических указаний.
Рецензент:
Бражников С.А., канд. техн. наук, доцент кафедры КиВТ;
Персидсков Г.М., нормоконтроль.
СОДЕРЖАНИЕ
1. Цель лабораторной работы ………………………….4
2. Описание методики решения задачи…………………. 4
3. Порядок выполнения лабораторной работы…………..8
4. Контрольные вопросы по лабораторной работе………8
5. Содержание отчета по выполнению лабораторной
работы……………………………………………………….9
Библиографический список……………………………….9
1. ЦЕЛЬ ЛАБОРАТОРНОЙ РАБОТЫ
Цель лабораторной работы: изучение и освоение методики решения задачи размещения одногабаритных модулей в монтажном пространстве (стадия непосредственного размещения) с оптимизацией по критерию минимума суммарной длины сигнальных связей между модулями и с заданным конструктивно-технологическим ограничением в виде наличия фиксированных модулей.
|
|
|
2. ОПИСАНИЕ МЕТОДИКИ РЕШЕНИЯ ЗАДАЧИ
Сформулированная в общем виде задача размещения заключается в определении положения модулей и внешних контактов в монтажном пространстве типовой конструкции (стадия непосредственно размещения) и определении конкретной геометрии печатного или проводного монтажа схемы (стадия трассировки).
Задача решается с учетом выбранного критерия оптимизации (минимум суммарной длины сигнальных связей, минимум длины самой длинной связи, минимум числа пересечений связей при произвольной их конфигурации, максимум числа цепей с возможно более простой конфигурацией, максимально близкое расположение модулей, имеющих наибольшее количество связей между собой). При решении задачи размещения должны учитываться заданные конструктивно-технологические ограничения.
Разбиение задачи размещения на две стадии (непосредственно размещение и трассировка) носит условный характер и вызвано трудностью решения всей задачи в целом. В данных методических указаниях описана методика решения задачи непосредственно размещения (первая стадия). Для этой методики выбран критерий минимума суммарной длины сигнальных связей, так как при его оптимизации косвенно минимизируются другие важные критерии
размещения, например длина связей и число их пересечений, а так же снижается искажение сигналов, что приводит к повышению надежности конструкции. В качестве конструктивно-технологического ограничения выступает возможность фиксации в заданных позициях конструктивного пространства заданных модулей.
Для размещения модулей выбрано монтажное пространство прямоугольной формы (что чаще всего бывает на практике). Это монтажное пространство является регулярным, т.е. позиции установки модулей фиксированы и имеют постоянный шаг, измеряемый в условных единицах (см. Рис. 1)
|
|
|
Рисунок 1- Эскиз монтажного пространства
На рис. 1 в позициях М1,…M12 установлены модули с номерами N1,…N12.
Считается, что соединения исходят из геометрических центров модулей, метрика – ортогональная, расстояния между соседними позициями по горизонтали и вертикали одинаковые. Тогда математической моделью монтажного пространства является граф решетки Gr (см. [ ]), а расстояния между позициями установки модулей вычисляются по формуле
Cij =|xi - xj| + |yi - yj|
где xi, yj – координаты позиций установки (посадочных мест) модулей.
Для достижения глобального оптимума по критерию минимума суммарной длинны сигнальных связей между размещаемыми модулями, т.е. для нахождения самого лучшего
варианта размещения, необходимо произвести полный перебор всех возможных вариантов размещения. Количество этих вариантов вычисляется по формуле
где N – количество размещаемых модулей, М – число позиций установки в монтажном пространстве. Для вычисления K использована формула вычисления количества размещений RNM, применяемая в комбинаторике. Для частного случая, в котором M=N, K равно количеству перестановок PM = M!, вычисляемому в комбинаторике.
Очевидно, что для больших значений N и соответственно M, количество вариантов размещения может оказаться столь велико, что решение задачи полным перебором оказывается нецелесообразным даже при использовании ЭВМ.
В данной методике для решения задачи размещения предлагается использование последовательного алгоритма для получения исходного варианта размещения, а затем итерационного алгоритма парных перестановок для оптимизации исходного варианта размещения. При этом гарантируется только получение только локального минимума по выбранному критерию.
При работе последовательного алгоритма в первую очередь размещаются фиксированные модули. Если таковых нет, должно сработать правило выбора начального модуля и позиции его установки. Например, установка в центральную позицию модуля с максимальным числом связей. Дальнейшая работа алгоритма состоит в поочередном выборе модулей, максимально связанных с уже размещенными и установке их в позиции, ближайшие к уже размещенным модулям. Для этого очередной размещаемый модуль устанавливается во все по очереди выбираемые свободные позиции и для каждой их них подсчитывается значение приращения целевой функции. Та позиция, для которой приращение целевой функции окажется минимальным, является предпочтительной.
|
|
|
Значение целевой функции, описывающей выбранный критерий оптимизации, для уже размещенных модулей, вычисляется как сумма произведений, каждая из которых состоит из двух сомножителей: количества связей между i -ым и j -ым модулями (берется из матрицы смежности S) и расстояния между k -ой и l -ой позициями установки i -го и j -го модуля соответственно (берется из матрицы расстояний C). Правило составления матрицы смежности S приведено в [1 ]. Матрица расстояний C – таблица, номерам строк и столбцов которой соответствуют номера позиций установки в монтажном пространстве. Значения элементов матрицы расстояний C ij вычисляются по правилу, приведенному выше.
Работа итерационного алгоритма парных перестановок состоит из следующих шагов.
Шаг 1. На исходном варианте разбиения (который является результатом работы последовательного алгоритма) производится очередная парная перестановка модуля i с модулем j (ни один из этих модулей не должен быть фиксированным). Количество таких неповторяющихся перестановок, которые можно выполнить на исходном варианте размещения равно
m = C2N = N(N-1)/2,
где N – количество размещенных модулей, C2N – количество сочетаний, вычисляемое в комбинаторике по формуле
CMN = N! / ((M - N)! M!)
Шаг 2. После каждой перестановки подсчитывается приращение целевой функции (описание целевой функции см. в описании работы последовательного алгоритма).
Шаг 3. После всех возможных перестановок определяется пара модулей, перестановка которых приводит к наибольшему улучшению целевой функции. Математически эта перестановка должна удовлетворять следующему условию:
|
|
|
Dkr = min {Di,j}; Dkr < 0;
i = 1,n-1
j =i+1,n
Шаг 4. В результате выполнения этой перестановки образуется новый улучшенный вариант размещения, принимаемый за начальный. Осуществляется переход к шагу 1 (выполняется следующая итерация).
Шаг 5. Алгоритм заканчивает свою работу вследствие выполнения, в зависимости от конкретной реализации алгоритма, одного из условий:
- исчерпано заданное число итераций;
- на очередной итерации достигнута заданная точность решения δ;
- на очередной итерации ни одна из возможных парных перестановок не привела к улучшению целевой функции, т.е.
D kr = min {Di,j} ≥ 0
Качество полученного решения во многом зависит от количества модулей, расположенных в монтажном пространстве, количества фиксированных
модулей, качества исходного варианта размещения, условия окончания работы алгоритма. Недостатком описанного алгоритма оптимизации размещения является сравнительно низкое качество полученного с точки зрения последующей трассировки. Представление информации о связях в схеме электрической принципиальной в виде матрицы смежности S не позволяет учитывать реальное расположение контактов размещаемых модулей в монтажном пространстве и их взаимную ориентацию, что очень важно при реализации печатных соединений.
Качество решения задачи непосредственно размещения существенно улучшается с точки зрения последующей трассировки, если при подсчете целевой функции и соответственно ее приращения учитывается длина сигнальных связей, соединяющих модули с электрическим соединителем (и ее приращение). В этом случае модули, имеющие связи с внешними выводами не окажутся на значительном удалении от них.
Точность решения задачи размещения модулей значительно возрастает при использовании в качестве целевой функции суммарной длины минимальных связующих деревьев, построенных на контактах каждой цепи. Это возможно при использовании ЭВМ с большим быстродействием, т.к. время счета по сравнению с описанным выше алгоритмом существенно возрастает.
3. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ
3.1. Изучить теоретическую часть данных методических указаний.
3.2. Подготовить необходимые для решения задачи исходные данные:
- матрицу смежности S, соответствующую индивидуальному варианту задания, взять из отчета по лабораторной работе "Представление информации о связях в схеме электрической принципиальной для ввода в ЭВМ";
- составить эскиз монтажного пространства, пронумеровав позиции установки модулей. Подготовить список их координат;
|
|
|
- составить перечень фиксированных модулей (с указанием позиций их установки).
3.3. Имитируя работу последовательного алгоритма, подготовить исходный вариант размещения.
3.4. Запустить на выполнение программу, реализующую итерационных алгоритм парных перестановок. Адрес программного файла взять у преподавателя.
3.5. Пройдя тестирование и задав все необходимые для работы программы исходные данные, получить результаты ее работы, а затем поместить их в пункт 3 отчета по лабораторной работе.Запустить несколько раз программу на выполнение, меняя исходный вариант размещения. Убедиться в том, что результат работы итерационного алгоритма парных перестановок зависит от исходного варианта размещения.
3.6. Оформить отчет по лабораторной работе
4. КОНТРОЛЬНЫЕ ВОПРОСЫ ПО ЛАБОРАТОРНОЙ РАБОТЕ
4.1. В чем заключается задача размещения? На какие составные части она разбивается и с чем это связано?
4.2. С учетом каких критериев оптимизации может решаться задача размещения?
4.3. Что вы знаете о конструктивно-технологических ограничениях, учитываемых при решении задачи размещения?
4.4. Что вы знаете об алгоритмах решения задачи размещения?
4.5. Дать характеристику используемой в изучаемой методике модели монтажного пространства. Чем различается ортогональная и эвклидова метрики?
4.6. Описать работу последовательного алгоритма размещения.
4.7. Описать работу итерационного алгоритма парных перестановок.
4.8. Как вычисляется целевая функция, соответствующая критерию суммарной длины сигнальных связей?
4.9. В чем заключается работа алгоритма полного перебора и почему его редко используют?
4.10. Описать недостатки использованной в лабораторной работе методики решения задачи размещения.
5. СОДЕРЖАНИЕ ОТЧЕТА ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНОЙ РАБОТЫ
Отчет по лабораторной работе должен содержать:
- титульный лист;
- пункт "Постановка задачи", в котором формируется поставленная задача и перечислены исходные данные для ее решения;
- пункт "Ход работы", в котором мотивируется выбор методики решения поставленной задачи, дается ее описание или приводится ссылка на необходимое описание в первоисточнике; в этом же пункте дается характеристика используемого программного продукта и перечислены исходные данные для программы;
- пункт "Результаты", в котором приведены результаты работы программы;
- пункт "Анализ результатов", в котором анализируется качество полученного решения, его полнота;
- пункт "Выводы", в котором дается оценка проделанной работы (перечислены ее достоинства и недостатки), даются рекомендации для получения более качественного решения, если такое возможно.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1 Представление информации о связях в схеме электрической принципиальной для ввода в ЭВМ. Методические указания к лабораторной работе./Е.А.Кожаев,Л.В.Иванова,изд.во СНТУ,2004-7с.
2 Савельев А.Я. Конструирование ЭВМ и систем: учебн. пособие – М.: Высш. Шк., 1984 – 247с.
3 Куземин А.Я. Конструирование и микроминиатюризация электронной вычислительной аппаратуры: учебн. пособие, М.: Радио и связь, 1985 – 279с.
|
|
|
