close

Вход

Забыли?

вход по аккаунту

?

Моделирование трехмерных температурных полей в электронных модулях.

код для вставкиСкачать
Программные продукты и системы
Режим
Простой анаглиф
Оптимизированный анаглиф
Затворные очки, квадробуфер
Поляризационная проекционная
система, режим horizontal span
Чересстрочный формат
Формат WowVx для мониторов
Philips 3D Solutions
№ 2, 2010 г.
Падение скорости
1.5
2.2
1.5
1.5
2.2
2
Из них следует, что накладные расходы на
моделирование стереорежима невелики и в среднем можно считать, что для моделирования стереорежима требуется удвоенная производитель-
ность видеоподсистемы по сравнению с обычным
монорежимом.
Литература
1. Хураськин И.А., Михайлюк М.В. Моделирование объемного видения в системах виртуального окружения: сб. тр.
НИИСИ РАН. 2007.
2. Computing Anaglyphs using Least Squares Approximation
in CIE Color Space. URL: http://research.csc.ncsu.edu/stereographics/LS.pdf (дата обращения: 01.11.2009).
3. 3D Interface Specifications White Paper. Philips 3D Solutions. Website: URL: www.philips.com/3dsolutions (дата обращения: 01.11.2009).
4. Михайлюк М.В., Торгашев М.А. и др. Система
GLView визуализации трехмерных виртуальных сцен: сб. трудов НИИСИ РАН. 2007.
УДК 621.396
МОДЕЛИРОВАНИЕ ТРЕХМЕРНЫХ ТЕМПЕРАТУРНЫХ ПОЛЕЙ
В ЭЛЕКТРОННЫХ МОДУЛЯХ
А.Г. Мадера, д.т.н.; П.И. Кандалов (НИИСИ РАН, г. Москва, alexmadera@mail.ru)
Статья посвящена методу математического и компьютерного моделирования трехмерных температурных полей
в сложных конструкциях реальных электронных модулей, содержащих многослойную печатную плату и установленные на ней интегральные микросхемы и электрорадиоэлементы. Метод моделирования реализован в виде программного пакета для персональных компьютеров, доведенного до уровня пользователя.
Ключевые слова: электронный модуль, математическое моделирование, программный комплекс, температурное поле.
Проектирование изделий электронной техники (ИЭТ) включает в себя решение многочисленных задач, таких как разработка и проектирование
логической и принципиальной электрической
схемы ИЭТ, трассировка сигнальных проводников
в слоях многослойной печатной платы (МПП),
выбор и/или конструирование микросхем (МС),
тепловое проектирование ИЭТ и многие другие.
Одной из основных структурных единиц ИЭТ
является электронный модуль (ЭМ), содержащий
МПП и установленные на ней МС и электрорадиоэлементы (ЭРЭ) (рис. 1). В силу значительной
температурной зависимости электрических параметров МС и ЭРЭ возникновение в конструкции
ЭМ температурного поля приводит к тому, что
важнейшие электрические характеристики ЭМ –
статические и динамические электрические параметры, надежность, быстродействие, помехоустойчивость и т.д. – претерпевают существенные
изменения. Поэтому снижение уровней температуры на элементах ЭМ является чрезвычайно актуальной задачей, для чего разработчиками предпринимаются различные меры:
понижение рассеиваемых в МС мощностей,
применение корпусов МС с малым тепловым сопротивлением,
установка на корпуса МС теплоотводов
(радиаторов),
интенсификация теплообмена путем установки высокотеплопроводных шин, тепловых
труб, применения обдува вентиляторами, жидкостного охлаждения и т.д.
Ребристый теплоотвод
Микросхемы
Электрические разъемы
Электрические
разъемы
МПП
Микросхемы
Рис. 1. Электронный модуль и его элементы
Для эффективного отвода тепловой энергии в
конструкциях ЭМ и обеспечения требуемого теплового режима необходимо прежде всего провести
тепловое проектирование, которое включает в себя решение следующих задач:
моделирование (математическое и компьютерное) температурных полей конструкции ЭМ и
ее элементов в различных условиях эксплуатации
и испытаний;
проектирование элементов и систем отвода
теплоты (конвективно-воздушного, кондуктивно29
Программные продукты и системы
№ 2, 2010 г.
воздушного, кондуктивно-жидкостного, кондуктивно-испарительного, жидкостного и т.д.);
конструирование системы эффективного
охлаждения элементов ЭМ и всей конструкции
ЭМ в целом.
Для того чтобы проектирование и конструирование элементов и систем отвода теплоты в
конструкциях ЭМ было возможным, необходимо
располагать эффективными универсальными и надежными методами математического и компьютерного моделирования температурных полей
сложных конструкций ЭМ, которые должны учитывать следующее.
Конструкция ЭМ представляет собой сложную систему, состоящую из большого числа элементов, многие из которых сами, в свою очередь,
являются сложными системами. Так, конструкция
микросхемы состоит из кристалла с созданной на
его поверхности системой p-n-переходов, металлизированной разводки, корпуса МС, выводов
кристалла и корпуса, элементов теплоотвода и охлаждения.
Элементы ЭМ характеризуются различными значениями потребляемых мощностей, размерами и пространственной конфигурацией, различными теплофизическими характеристиками материалов, неоднородными включениями и полостями, нестационарным распределением потребляемых элементами мощностей как во времени, так и
в пространстве и т.д.
МПП и МС, определяющие работоспособность и эксплуатационные характеристики ЭМ,
представляют собой многослойные структуры, состоящие из большого числа слоев различной толщины и выполненные из разнородных материалов.
В статье рассматривается метод математического и компьютерного моделирования трехмерных температурных полей сложных конструкций
ЭМ с заранее заданной точностью, учитывающих
реальные конструктивные особенности корпусов
МС, условия их монтажа на поверхности МПП,
особенности крепления МПП в ЭМ, блоках и панелях, конструкции отвода теплоты от элементов
ЭМ. Для проведения компьютерного моделирования температурных полей ЭМ разработан программный комплекс на языке Delphi для персональных компьютеров, который не имеет аналогов
в российской и зарубежной практике теплового
проектирования ЭМ. В отличие от существующих
программных комплексов моделирования температурных полей в ЭМ (Beta-Soft, АСОНИКА и др.)
количество слоев в МПП, количество МС и ЭРЭ
не ограничено.
Моделирование ЭМ
Тепловые модели элементов ЭМ. Элементы
ЭМ, установленные на МПП, делятся на активные, характеризующиеся внутренним тепловыделением (МС, диоды, транзисторы, резисторы, катушки индуктивности, трансформаторы), и пассивные, не обладающие собственным тепловыделением (электрические разъемы, конденсаторы,
теплоотводы, металлические детали, тепловые
трубы). При моделировании теплообмена пассивные элементы выполняют функции теплоотводов
и по своей физике являются стоками теплоты, а
активные элементы, выделяющие тепловую энергию, – источниками теплоты.
Активные и пассивные элементы моделируются посредством тепловых схем (рис. 2), полу-
МС в корпусе
Тепловая модель
МС
Окружающая среда
Зазор между
МПП и МС
МПП
Тепловая модель
стока
Температура
стока
Выводы корпуса МС
Мощность
МС P
R
R
Корпус МС
Сток теплоты
Кристалл МС
Зазор между
МПП и МС
Выводы
корпуса МС
Rd
R
R
leads
Источник теплоты
МПП
МПП
Тепловая модель МПП
Рис. 2. Тепловые модели ЭМ, МПП, активных и пассивных элементов ЭМ
30
ca
jc
cp
Программные продукты и системы
чаемых методом электротепловой аналогии [1].
Для активных элементов (МС) мощность, потребляемая ими и полностью рассеиваемая в виде тепловой энергии, моделируется независимым источником потока теплоты мощностью Р; тепловой
тракт от кристалла МС к корпусу моделируется
тепловым сопротивлением переход–корпус Rjc
(junction-case); конвективный теплообмен с поверхности корпуса МС в среду или с поверхности
корпуса через теплоотвод, установленный на МС,
в среду моделируется тепловым сопротивлением
корпус–среда Rca (case-ambient); теплопередача от
основания корпуса МС к поверхности МПП моделируется двумя, параллельно соединенными тепловыми сопротивлениями, причем Rleads моделирует передачу теплового потока через выводы
корпуса (leads – выводы), а Rcp – передачу теплового потока от корпуса МС к плате через зазор
между корпусом МС и МПП (cp – case-plate). Тепловые сопротивления Rjc и Rca приводятся в
справочных данных на МС, и их значения могут
быть также получены моделированием или экспериментально. Для адекватного моделирования активных элементов, установленных на поверхностях МПП, необходимо учитывать, что между
элементом ЭМ и поверхностью МПП в пределах
площадки, соответствующей элементу, конвективный теплообмен со средой отсутствует. Тепловая модель пассивных элементов ЭМ содержит
одно тепловое сопротивление Rd (рис. 2), моделирующее полный тепловой тракт, вдоль которого
тепловая энергия отводится от МПП, далее через
конструкцию пассивного элемента к стоку теплоты в конце тракта, имеющего температуру Tcd, которая в общем случае может отличаться от температуры среды около МПП.
Тепловая модель МПП представляет собой
многослойную структуру (рис. 2), состоящую из
множества тонких разнородных слоев различной
толщины, количество которых достигает нескольких десятков. С верхней и нижней поверхностей
многослойной структуры МПП происходит конвективный теплообмен в среду.
Слои в многослойной структуре МПП могут
быть четырех видов: диэлектрические полиимидные слои с теплопроводностью; медные энергетические слои для земли и питания; сигнальные слои
с металлическими сигнальными проводниками
прямоугольного сечения, разделенные диэлектриком; теплоотводящие, сравнительно толстые медные слои.
Тепловая модель многослойной структуры
МПП и реальная конструкция МПП полностью
совпадают и представляют собой многослойный
прямоугольный параллелепипед (рис. 2) толщиной
d и размерами Lx и Ly по осям X и Y, имеющий М
слоев, при этом каждый i-й слой (i=1, 2, …, M)
имеет толщину di (d=d1+d2+ +dM) и коэффициент теплопроводности λi, Вт/м·К.
№ 2, 2010 г.
Помимо слоев, выполненных из однородных
материалов, реальная конструкция МПП включает
в себя сигнальные слои, которые имеют композитную структуру, состоящую из сигнальных металлических проводников прямоугольного сечения и диэлектрических слоев. Расположение сигнальных проводников в слое диэлектрика соответствует маршруту их трассировки, различному для
разных слоев, поэтому теплопроводность композитного слоя является анизотропной и различной в
каждой точке слоя и вдоль осей X и Y.
Для того чтобы моделирование температурных полей композитных слоев МПП было возможным, необходимо от анизотропной теплопроводности слоя перейти к эффективной усредненной величине теплопроводности эфф. Концентрация металлических проводников в слое и их местоположение изменяются от слоя к слою и поэтому являются стохастическими с точки зрения
МПП, что делает задачу определения эффективной теплопроводности каждого слоя довольно
сложной.
Однако в ряде случаев расчет величины эфф
тепловой модели МПП с достаточной для практики точностью можно проводить по формуле ожидаемой величины эфф= 1 1+ 2 2, 1+ 2=1, где
1 и 2 – теплопроводности металлического проводника и диэлектрика, занимающих в объеме
композитного слоя доли, равные 1 и 2 соответственно.
На верхней и нижней сторонах тепловой модели МПП расположены прямоугольные площадки, соответствующие активным и пассивным элементам ЭМ. Для общности моделирования принято, что температура среды и условия теплообмена
на верхней и нижней поверхностях МПП различны. Зависимость теплофизических параметров материалов тепловой модели, а также мощностей активных элементов ЭМ от температуры не учитывается.
Математическая модель теплообмена в тепловой модели МПП. Математическая модель,
описывающая трехмерное стационарное температурное поле Ti=Ti(x, y, z) в каждом i-м слое тепловой модели МПП, представляет собой систему
уравнений.
Уравнение теплопроводности в i-м слое
2
2
i
2
2
i
2
i
0 , i=1, 2, …, M.
x
y
z
Граничные условия на верхней (i=1) и нижней (i=M) поверхностях тепловой модели МПП, с
которых происходит теплообмен в среду по закону Ньютона, одновременное поступление тепловой энергии через источники теплоты в МПП и
отвод тепловой энергии от стоков теплоты, расположенных на поверхностях МПП, суммарная
мощность которых равна Р1 для i=1 (верхний слой
МПП) и РМ – для i=М (нижний слой МПП):
2
31
Программные продукты и системы
1
1
z
1( 1 z d
1
z d1
M
M
z
k
P1
№ 2, 2010 г.
a1 )
M( M z 0
1
a2 )
Ts,1
Td,1
Ts,2
Td,2
Pd=C(Td–Tcd), в которой Ts=
, Td=
,
...
...
Ts,N
Td,M
,
M
,
z 0
Pj1h j1
PjM h jM
l
, PM
j 1 l x j1 l y j1
j 1 lx jM ly
.
jM
Граничные условия на границе i-го и i+1-го
слоев тепловой модели МПП, выражающие равенство температур и потоков теплоты на стыке двух
соседних слоев:
iz 0
i 1z d
i
,
1
i
i
z
i 1
i 1
z 0
z
.
z di
1
Адиабатические граничные условия на боковых торцах тепловой модели МПП, полученные
в результате допущения о пренебрежимо малом
конвективном теплообмене с торцов МПП по
сравнению с конвекцией с поверхностей (верхней
и нижней) МПП:
y Ly
x Lx
i
x
i
x 0
y
0,
y 0
где Pj1, PjM – мощности j-го источника (s) или стока (d) теплоты на верхней и нижней поверхностях
тепловой модели МПП с размерами по осям X и
Y, равными lx j1 , ly j1 и lx jM , ly jM соответственно;
1,
M и T 1, T M – коэффициенты теплоотдачи и
температуры среды с верхней и нижней поверхностей тепловой модели МПП; hj – функция Хевисайда, равная 1, если точка на поверхностях тепловой модели МПП с координатами (xj, yj) принадлежит источнику теплоты, и равная 0 в противном случае, то есть hj=1, если (xj, yj) Pj, и
hj=0, если (xj, yj) Pj.
Особенность математической модели ЭМ состоит в том, что температура в произвольной точке тепловой модели ЭМ зависит от мощностей,
поступающих в МПП от активных элементов через источники теплоты, а также мощностей, которые отводятся от МПП через пассивные элементы,
то есть через стоки теплоты. В то же время мощности в источниках и стоках теплоты зависят от
температур, усредненных по площади источников
и стоков. Поэтому для того чтобы иметь возможность моделирования температурного поля в любой точке конструкции ЭМ, необходимо прежде
всего выразить средние по площади источников и
стоков температуры через мощности источников и
стоков теплоты, которые сами, в свою очередь, зависят от искомых значений средних температур
источников и стоков.
Математическая модель теплообмена конструкции ЭМ может быть записана в матричном виTs
Rss Rsd Ps
де:
, Ps=AP+B (Ts–Ta),
Td
Rds Rdd Pd
32
Ps,1
Pd,1
Ps,2
Pd,2
Ps=
, Pd=
...
...
Ps,N
Pd,M
– векторы температур, ус-
редненных по площадям источников теплоты Ts и
стоков теплоты Td, и векторы мощностей источников Ps и стоков Pd теплоты, расположенных на
поверхностях МПП; Rss, Rsd, Rds и Rdd – квадратные и симметрические матрицы, выражающие тепловое взаимодействие между всеми источниками
теплоты (Rss), между всеми источниками и стоками теплоты (Rsd), между всеми стоками и источниками теплоты (Rds) и между всеми стоками теплоты (Rdd). Элементы матриц известны априори и
рассчитываются на основе точного аналитического решения, получаемого методом двойного косинус-преобразования Фурье [2]; матрицы А, В и С
Ta,1
Tcd,1
P1
Ta,2
Tcd,2
P2
диагональные; Ta=
, Tcd=
, P=
...
...
...
PN
Ta,N
Tcd,M
– векторы заданных и известных априори температур среды, температур охлаждения стоков и
мощностей P, потребляемых активными элементами.
Конечной целью решения матричной математической модели ЭМ является определение мощностей всех источников Ps и стоков Pd теплоты,
расположенных на тепловой модели МПП, а после
того как они будут найдены, определение искомых значений температур в любой точке конструкции ЭМ, то есть в любой точке МПП на активных и пассивных элементах (кристаллах МС, корпусах МС и т.д.), а также значений температур,
усредненных по площадям источников и стоков
теплоты. В математической модели известными
величинами являются: блочная матрица с матрицами-блоками Rss, Rsd, Rds, Rdd; элементы матриц
А, В и С; векторы температуры среды Ta и температуры охлаждения стоков Tcd; вектор мощностей
P активных элементов ЭМ. Неизвестными величинами, подлежащими определению, являются:
векторы усредненных температур источников Ts и
стоков Td; векторы мощностей источников теплоты на МПП Ps и мощностей стоков теплоты на
МПП Pd.
В математической модели теплообмена конструкции ЭМ векторы усредненных температур источников Ts и стоков Td зависят от неизвестных
значений мощностей источников Ps и стоков Pd, а
те, в свою очередь, от неизвестных усредненных
температур источников Ts и стоков Td. Блочная
матрица математической модели, состоящая из
Программные продукты и системы
матриц Rss, Rsd, Rds, Rdd, как правило, плохо обусловлена, поэтому использование точных методов
для решения уравнений математической модели
не всегда приводит к правильному решению, неэффективно и неустойчиво.
Авторами разработан новый метод решения
уравнений математической модели, который эффективно достигает цели как для плохо обусловленных матриц, так и для матриц, норма которых
больше единицы. В первом случае обычные методы не позволяют найти решение уравнений из-за
проблем с устойчивостью и расходимостью, а во
втором – используемые итерационные методы
расходятся. Предложенный численный метод решения уравнений математической модели основан
на идее последовательных приближений и исполь-
№ 2, 2010 г.
зует комбинацию методов релаксации и половинного деления [3]. Моделирование, проведенное
для различных конструкций ЭМ с помощью разработанного метода, показало его эффективность,
быструю сходимость к искомому решению (в ряде
случаев за 3–5 итераций), а также независимость
метода от меры обусловленности матрицы системы уравнений математической модели.
Литература
1. Мадера А.Г. Моделирование теплообмена в технических системах. М.: НФ им. акад. В.А. Мельникова, 2005.
2. Кандалов П.И., Мадера А.Г. Моделирование температурных полей в многослойных структурах // Программные
продукты и системы. 2008. № 4 (84). С. 46–49.
3. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы
линейной алгебры. М.: Физматгиз, 1960.
УДК 519.1, 519.8, 793.7, 612.821
РАСТУЩИЕ ИНДУКТОРНЫЕ ПРОСТРАНСТВА
И АНАЛИЗ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ
(Работа выполнена при поддержке РФФИ, грант № 07-01-00101-a)
А.В. Коганов, к.ф.-м.н. (НИИСИ РАН, г. Москва, akoganov@yandex.ru)
Вводятся критерии эффективности использования параллельных алгоритмов при расчете логических и математических функций. Для анализа этих критериев предлагается аппарат растущих индукторных пространств. Подробно
рассмотрены две задачи с эффективной и малоэффективной параллельностью алгоритмов.
Ключевые слова: алгоритмы, параллельность, эффективность, вычисления, тесты.
Рассматриваемая математическая задача возникла при разработке тестов инженерной психологии, направленных на выявление людей, способных одновременно выполнять несколько операций распознавания при обработке визуальной
текстовой информации. С точки зрения математики проблема сводится к поиску логических функций двух типов. Одни функции должны допускать
значительное ускорение решения при одновременном использовании нескольких процессоров,
выполняющих распознавание символов исходной
информации и операции некоторого логического
базиса. Другие требуют для этого очень большого
увеличения ресурсов при низкой средней эффективности на один процессор. Требуется также,
чтобы каждая задача допускала вариацию в широких пределах объема исходной информации. Тесты были построены, проведен эксперимент, показавший эффективность методики [1–3]. Рассмотрим математический аппарат анализа логических
функций для выявления задач указанных типов.
Каждый алгоритм вычисления функции – это процесс на индукторном пространстве [4–5]. Использование в алгоритме операций условных переходов делает удобным введение понятия растущего
индукторного пространства, где на каждом такте
вычислений добавляются необходимые элементы
индукции.
Понятие характеристики задачи
Под задачей будем понимать алгоритм, определяющий функцию от конечного (но переменного и неограниченного) числа переменных (входов).
Все входы и значения примеров (ответы) принимают конечное число значений в некотором фиксированном (базовом) алфавите. Каждый набор
значений переменных определяет один пример задачи. Для вычисления ответов примеров задачи
используется заданный набор элементарных операций, образующих логический базис в базовом
алфавите, необязательно минимальный (операционный базис). Реализацией примера задачи будем
называть итеративную структуру элементарных
операций, построенную как направленный граф
без циклов. Вершины графа распадаются на уровни (уровни вложенности). Вершинам графа начального уровня сопоставлены элементы исходных данных. Вершинам последующих уровней
сопоставлены операции из операционного базиса.
Стрелки показывают, как передаются данные в аргументы этих операций – от элементов исходных
данных или от результатов операций предыдущих
33
Программные продукты и системы
уровней. В связи с тем, что порядок аргументов
операции в общем случае существенен для результата, операция должна различать и упорядочивать стрелки, входящие в вершину, с которой
она ассоциирована. Операции последнего уровня
выдают ответ. Далее рассматривается операционный базис, состоящий из всех логических функций от некоторого фиксированного числа k переменных со значениями в базовом алфавите (значение k будет емкостью элементарных операций).
Глубиной реализации назовем максимальный
уровень вложенности операций в ней. Начальный
уровень исходных данных считается нулевым.
Запараллеленностью реализации назовем максимальное число операций одного уровня вложенности.
Оптимальная по глубине реализация примера
– это реализация наименьшей (оптимальной) глубины при заданном классе элементарных операций и заданной запараллеленности. Функциональная зависимость оптимальной глубины от запараллеленности – характеристика данного примера из задачи. T(k, P) – характеристика задачи,
время решения примера задачи с запараллеленностью P на операциях емкости k. Когда параметр k
фиксируется, его можно не указывать. Эффективность запараллеленности определяется абсолютной и относительной удельной эффективностью
на один дополнительный процессор:
T k,1 T k, P
D k, P
;
(1)
P 1
T k,1 T k, P
D k, P
.
(2)
d k, P
T k,1 P 1
T k,1
Замечание: в некоторых задачах граф оптимальной реализации можно выбирать в зависимости только от числа входов, но не от значений
входных данных; в других задачах такой граф будет различным для разных наборов значений входов.
Задача с эффективной запараллеленностью
Высокой эффективностью запараллеленности
обладает задача поиска наименьшего (или наибольшего) числа в строке или в таблице чисел:
F(x1, …, xn)=min{x1, …, xn}.
(3)
Если обозначить S(xk, …, x1) операцию емкости k сравнения k однозначных чисел из цифрового алфавита, например {0; 1; 2; 3; 4; 5; 6}, S(xk,…,
x1)=min{xk,…, x1} или S(xk, …, x1)=max{xk, …,
x1}, то последовательная реализация имеет вид
F(x1, …, xn)=S(xn, …, xn-k+2, S(xn-k+1, …, xn-2k+3,
S(…S(xk, …, x1)…))).
(4)
Запараллеленность P может быть реализована
в виде (4) с разбивкой всего набора чисел на P
равных частей (возможно, последняя будет меньше), с последующим поиском минимума из P чисел (предварительных результатов) с запараллеленностью P:
34
№ 2, 2010 г.
F(x1, …, xn)=F(F(x1, …, xkP), …,
F(xk(P-1)+1, …, xn)).
(5)
Последний этап можно реализовать древовидной итерацией операций S с ветвлением до P. Легко доказать, что это оптимальная реализация по
глубине и по числу операций одновременно:
n
T(k,1)
. Характеристика задачи (3) (с точk 1
ностью до целочисленного округления):
log P
n
;
(6)
T n,k,p
k 1 P log k
D n,k, P
d n,k, P
n
k 1 P
1
P
logk P
P 1
;
logk P k 1
n P 1
(7)
.
(8)
Для характерных в эксперименте значений
n=10, k=2 эффективность параллельности будет
следующая:
P=2; D=4,00; d=40 %,
(9)
P=3; D=2,48; d=25 %,
(10)
P=4; D=1,94; d=19 %,
(11)
где P – число процессоров; D – удельная эффективность на один дополнительный процессор; d –
относительная удельная эффективность.
Из характеристик (9–11) видно, что эффективность высока, особенно при введении второго и
третьего процессоров.
Растущие индукторные пространства
Для задач, в которых реализация зависит от
исходных данных, удобно ввести понятие растущего индукторного пространства. Смысл этого
понятия в том, что новые точки и элементы индукции вводятся по мере обработки входной информации. Этот эффект хорошо известен в программировании при использовании операций условного перехода. В зависимости от полученных
промежуточных результатов к вычислениям подключаются те или иные программные блоки. Если
построить развертку реализации алгоритма по
тактам с указанием переходов от одной операции
к другой и источников операндов для очередной
операции, то получится индукторное пространство, в котором вычисление представлено процессом типа индукторного автомата. Но разным исходным данным будут соответствовать в общем
случае разные пространства и автоматы в зависимости от реализации условных переходов в программе. Дадим формальное определение этого явления.
Обозначения. A – алфавит, в котором определены значения операндов и результатов всех операций; k – емкость операций, то есть максимально
возможное число операндов; H(A, k) – класс всех
операций в заданном алфавите и с заданной емкостью (базовые операции); n – число входов при-
yk )
Программные продукты и системы
№ 2, 2010 г.
мера задачи (число аргументов вычисляемой
функции, число точек нулевого уровня в реализации); P – запараллеленность (максимально допустимое число операций на одном уровне реализации); V(A, n, k, P) – класс операций порождения
реализации при ограничениях, заданных указанными параметрами (определение 1); U(A, n, k, P)
– класс алгоритмов роста.
Определение 1. Операция порождения реализации u(s; x1, …,xk) V(A, n, k, P) имеет операнды
xi A, i=1, …, k, s {0; 1; …} и выдает значения
вида (i1, s1), …, (ik,sk); w , где w H(A, k) и для
всех j=1,…, k выполнены следующие ограничения: 0 sj<s; 1 ij n при sj=0; 1 ij P при sj 1.
Определение 2. Алгоритм роста из U(A, n, k,
P) – это рекурсивная функция построения уровней
индукторного пространства реализации решения
по набору входов примера задачи. Алгоритм
удовлетворяет следующим требованиям.
1. Уровень L0 состоит из n точек t10 ,...,t n0 без
индукторов (это граница индукторного пространства реализации). Если входы примера имеют значения a1, …, an, то точке t 0i сопоставим состояние ai.
2. Уровень L1 состоит из P точек t11 ,...,t1P .
Каждой точке t 1i сопоставлен индуктор, содержащий, кроме этой точки, ровно k точек t0j(1) ,...,t 0j(k)
уровня L0. Каждой точке t 1i сопоставлены операция порождения w 1i из V(A, n, k, P) и нумерация
точек индуктора. Состоянием процесса вычисления в этой точке будет y1i w1i (a0j(1) ,...,a0j(k) ) . Каждой точке t 1i сопоставлены операция u1i из V(A,
n, k, P) и нумерация точек индуктора. Построение
следующего слоя ведется по значениям
u1i (2;a0j(1) ,...,a0j(k) )
i1i ,s1i ,..., iki ,ski ;wi .
3. Пусть построены уровни L0, …, Ls-1. Все
слои, кроме нулевого, содержат P точек. Каждой
j
точке t i , i {1; …; P}, j=1, …, s-1, сопоставлены
j
операция порождения w i из V(A, n, k, P) и нумерация точек индуктора. Состоянием процесса выj
j
числения в этой точке будет y i w i (y1 , ..., y k ) ,
где аргументы соответствуют значениям процесса
в точках индуктора, отличных от центра индукции. Каждой точке t si 1 сопоставлены операция
u si 1 из V(A, n, k, P) и нумерация точек индуктора. Построение следующего слоя ведется по значениям
кортежа
usi 1 (s;y1 ,..., yk )
i1i ,s1i ,...,
i1i ,s1i ,..., i ki ,ski ;w i . Такому значению сопоставляется
точка t si слоя Ls с индуктором
si
si
1
k
t si ;t i i1 , ..., t i ik
и
указанным порядком точек индуктора. Этой точке
также сопоставляется операция w si w i с тем же
порядком аргументов. Конец определения.
Алгоритм роста из U(A, n, k, P) формирует
индукторное пространство реализации запараллеленности P, используя только операции порождения емкости k. Для каждой исследуемой задачи
надо выбрать из класса U(A, n, k, P) подкласс решающих ее алгоритмов. На этом подклассе надо
оценить характеристику задачи.
Потенциальное и универсальное
пространства реализаций
Определение 3. Потенциальным пространством реализаций (ППР) ранга [n, k, P] называется
индукторное пространство, в котором граница состоит из n точек и в котором для любой возможной реализации с соответствующими параметрами
есть изоморфное подпространство.
Определение 4. Универсальным пространством реализаций (УПР) ранга [n, k, P] называется
пространство, в котором граница состоит из n точек и для любой возможной реализации с соответствующими параметрами можно реализовать эквивалентный процесс (в смысле возможности взаимного пересчета состояний точек при некоторой
биекции точек реализации и УПР [5, 6]).
Теорема 1. Универсальное пространство определено однозначно своим рангом с точностью
до полных индукторов точек. Оно является объединением счетного числа не пересекающихся попарно подмножеств (назовем их уровнями)
T=L0 L1 …, где L0=n; Li=P для i 1. Элементы
индукции (полные индукторы) имеют вид [t,
{t} L0 … Ls-1]I для t Ls, s 1.
Доказательство. Поскольку требуется изоморфизм процессов на реализации и на универсальном пространстве, каждому уровню графа
реализации должно соответствовать равное по
числу элементов подмножество из УПР, и эти
подмножества должны быть не пересекающимися
попарно. Так как индуктор точки пространства
реализации может содержать любые k элементов
из предыдущих уровней, в УПР полный индуктор
точки должен содержать объединение всех предыдущих уровней. Процесс реализации формируется по схеме построения растущего пространства,
но вместо порождения новой точки и элемента
индукции используется очередная точка следующего уровня. В точках тех уровней, которых нет в
реализации, процесс на УПР задается как тривиальный (с одним состоянием). Конец доказательства. i
i
i k ,ski ;w
Замечание: имеется бесконечно много неизоморфных УПР одного ранга, которые различаются
наборами неполных индукторов каждой точки.
35
Программные продукты и системы
№ 2, 2010 г.
Теорема 2. Имеется единственное минимальное потенциальное пространство реализаций. Оно
является объединением попарно не пересекающихся подмножеств (уровней) T=L0 L1 …, где
L0=n. Каждому подмножеству {t1; …tk} L0 …
Ls-1, содержащему k точек из L0 … Ls-1, взаимно однозначно соответствует одна точка t Ls
уровня Ls с индуктором {t; t1; …tk}. Это порождающая система индукторов.
Доказательство. Поскольку требуется наличие в ППР подпространства, изоморфного любой
реализации с указанными параметрами, и в различных реализациях возможны любые индукторы
вида {t; t1; …tk}, где {t1; …tk} L0 … Ls-1, t Ls,
то в любом ППР должны быть указанные в формулировке теоремы уровни (доказывается индукцией по номеру уровня). Тот факт, что такое пространство является ППР, доказывается прямым
инъективным вложением в него любой реализации
последовательно по слоям с учетом индукторов
точек реализации. Конец доказательства.
Замечание: имеется бесконечно много неизоморфных ППР, которые получаются произвольным расширением минимального ППР без изменения системы индукторов на минимальном ППР.
Утверждение 1. В минимальном ППР число
ns точек слоя Ls удовлетворяет рекуррентному
гипергеометрическому соотношению
k
.
(12)
ns 1 P
n n1 ... ns
Доказательство. На слое Ls необходимо
иметь одну точку для каждого набора из k точек
из объединения предыдущих слоев и для каждого
из P процессоров слоя. Конец доказательства.
В соответствующем растущем пространстве
слой содержит только P точек.
Задача с неэффективной
запараллеленностью
Описание задачи слежения. Данные примера в
задаче слежения оформлены как прямоугольная
таблица M N, где M – вертикаль, N – горизонталь
(см. рис. 1). В каждой клетке таблицы стоит знак
из алфавита +0–. В крайнем левом столбце одна из
клеток дополнительно помечена символом (*).
Рядом с крайним правым столбцом правее стоят
метки из алфавита A B C D, образующие N+1-й
Прямоугольная таблица с
данными примера задачи
Рис. 1
36
Фрагмент треугольной
таблицы
столбец. Эти метки повторяются циклически в
строках 1,…,M.
Задание: проследить от меченой левой клетки
траекторию до правого столбца меток и выдать
тот символ, который стоит в финишной правой
клетке. Траектория строится так: из клетки со знаком (+) надо перейти в правый соседний столбец
на строку выше; из клетки со знаком ( ) переход
вправо на строку ниже; знак (0) означает переход
вправо в ту же строку. В примере запрещено указывать выход за верхнюю или нижнюю границы
таблицы. Формально переход из клетки с координатами (i, j) (строка, столбец) описывается так:
i, j
i 1, j 1 a ;
i, j
i, j 0
(i 1, j 1) a ;
(13)
i, j 1 a .
Символ в правых скобках показывает, что записано в клетке. Для неграничных клеток a {+; 0; –}.
В граничном случае
1, j a a 0; ;
M, j a
i, N 1 a
a {0; };
a
(14)
A;B;C;D .
Расчет характеристики задачи слежения.
Использование запараллеленности в задаче слежения возможно только путем предварительного
расчета нескольких отрезков траектории в середине или в конце таблицы. Когда основная траектория, идущая от начальной левой клетки с меткой
(*), попадет в начало такого отрезка, ее можно
сразу перенести в конец этого отрезка. В этой
схеме эффект явно вероятностный: попадет ли основная траектория в заранее заготовленный отрезок. Однако расчет характеристики задачи проводится по худшему случаю. Тогда требуется, чтобы
дополнительные процессоры гарантированно рассчитывали продолжение траектории из всех точек,
в которые может попасть начальный участок траектории, рассчитываемый основным процессором.
Такую совокупность начальных точек для гипотетического продолжения траектории назовем потенциальной границей (п-граница) траектории.
После переноса основного процессора в заранее
вычисленную последнюю точку продолжения траектории можно повторить для нее, как для корня
процесс параллельного расчета из точек новой
границы.
Для расчета характеристики этой задачи вначале рассмотрим случай расчета траектории на
треугольной таблице (Т-табло) с числом уровней
N от корня (нулевой уровень). В задаче на Т-табло
отсутствует краевой эффект выхода на нижнюю
или верхнюю границу таблицы.
Определение 5. Относительным рангом п-границы для данной начальной точки назовем наименьшее по траекториям число уровней от начальной точки до точки п-границы.
Программные продукты и системы
Утверждение 2. Наименьшая по числу точек
п-граница данного относительного ранга s – это
уровень s на Т-табло с корнем в начальной точке.
(Доказывается индукцией по рангу.)
Следствие. При заданной запараллеленности
в оптимальном по характеристике алгоритме решения задачи слежения дополнительные процессоры отслеживают траектории из точек некоторого уровня s.
Доказательство. Допустим, процессоры на
начальном такте распределены по некоторой
п-границе уровня s. Тогда имеется траектория при
неких исходных данных, для которой встреча с
границей происходит на такте s. В этом случае все
дополнительные процессоры надо перестраивать
на новую п-границу новой начальной точки. Таким образом, в расчете на самый плохой случай
число тактов решения задачи будет не лучше, чем
при распределении процессоров по уровню s. По
утверждению 2 для этого заведомо хватит процессоров. Конец доказательства.
Замечание: при достаточно большом числе
процессоров, если позволяет длина траектории N,
можно вести расчет траекторий сразу с нескольких п-границ (обозначим их число r). При этом по
числу тактов решения задачи оптимально делать
одинаковые расстояния x= s между границами.
Тогда по истечении s тактов можно перенести начальную точку сразу на rx уровней, затратив
только r дополнительных тактов (см. рис. 2). На
основе этих фактов можно рассчитать характеристику T(P) задачи слежения.
T(1)=N.
(15)
Примечание: линия ZZ – начальная часть главной траектории; столбец AB – первая п-граница; столбец A B – вторая
п-граница; длина строки от начальной клетки до п-границы
равна x, r=2.
Рис. 2. Совместная работа нескольких процессоров
Объем исходных данных n=1+2N(N+1) для
Т-табло, а для прямоугольной таблицы n=(N+1)M.
Емкости операции k=1 (операция обрабатывает
одну клетку или выход одного процессора). Число
одновременно обрабатываемых п-границ обозначим r. Расстояния по уровням s между границами
обозначим x= s. На Т-табло число точек уровня s
от любой начальной точки:
№ 2, 2010 г.
v(s)=2s+1
P=1+ v(x)+ v(2x)+…+ v(rx),
P(r, x)=r+1+xr(r+1).
Условная характеристика задачи:
x r
.
T* (r, x)
N
(r 1)x
Характеристика задачи:
T(P, N)
minr,x
P(r,x) P
T* (r, x) |N .
(16)
(17)
(18)
(19)
Можно определить приведенную характеристику:
t(p)=T(P)/N,
(20)
D(P)
1 t(P)
d(P)
.
(21)
N
P 1 N 1
Аналитическое решение задачи (19–21) (поиск
для (19) экстремума) приводит для r(P) к уравнению четвертой степени. Но возможно численное
решение с учетом ограничений на вероятные значения запараллеленности (17). Для больших N
проведены расчеты эффективности для начальных
значений запараллеленности. При малых N эффективность ниже. Во всех случаях показана низкая эффективность. При числе процессоров меньше шести эффекта вообще нет. При P=6 эффект
составил t(P)=75 % по времени и d(P)=5 % по
процессорам. При P=18 время t(P)=56 % и не меняется при увеличении числа процессоров до 22.
Удельная эффективность падает с d(18)=2,5 % до
d(22)=2 %.
Задача слежения на прямоугольной таблице и
в полосе. Построение п-границ (слоев) на полосе
ширины M или в таблице M N требует учета выхода траекторий на границу. При малых продольных смещениях L от начальной точки на средней
линии полосы (таблицы) выхода за границу нет.
Это соответствует условию 1+2L M. При алгоритме решения с r п-границами и расстоянием x
между ними это условие соответствует по (16)
значению L=xr. Тогда
M 1
r
m(x) ,
(22)
2x
P(r, x)=r+1+xr(r+1).
(23)
После выхода возможных траекторий на границу полосы каждая п-граница имеет длину M.
Приведенные характеристики сохраняют вид (20)
и (21). При r>m(x)
P(r, x)=m(x)+1+xm(x)(m(x)+1)+(r–m(x))M, (24)
T* (r, x)
1
1
t* (r, x)
.
(25)
N
r 1 x
*
При больших x значение m(x)=0 и t убывает,
поэтому
1
t(P) ~ t* (r, )
,
(26)
r 1
P 1
где r
,x
.
M
37
Программные продукты и системы
По этим формулам рассчитаны характеристика задачи и эффективность запараллеленности для
двух значений ширины полосы M=4 и M=8 при
N>>1, которые удобны для теста. Удельная эффективность дополнительных процессоров для
M=4 варьируется от d(P)=12,5 % при P=5, r=1,
t(P)=50 %, до d(P)=2,8 % при P=33, r=8,
t(P)=11 %. Для M=8 для r=1, P=9 эффект
t(P)=50 %, d(P)= 6,25 %, а для r=8, P=65 эффект
t(P)=11 %, d(P)=1,39 %. При этом эффект возникает только при достаточно больших (указанных)
начальных запараллеленностях, и эффективные
значения P нарастают с шагом M. Таким образом,
параллельный счет задачи слежения неэффективен.
№ 2, 2010 г.
Литература
1. Коганов А.В., Пятецкий-Шапиро И.И., Фейгенберг
И.М. Зависимость скорости решения от сложности и способа
кодирования исходных данных // Вопросы экспериментального исследования скорости реагирования. Тарту, 1971.
2. Коганов А.В. Коллективы автоматов в детерминированных и случайных средах и приложение к психологическим
тестам: дис. … канд. физ.-мат. наук. М., 1972.
3. Коганов А.В. Исследование возможности параллельного выполнения логических операций человеком. Параллельные
вычисления и задачи управления // РАСО–2001: тр. междунар.
конф. (2–4 октября 2001 г., Москва). М.: ИПУ РАН, 2001.
4. Коганов А.В. Индукторные пространства и процессы //
ДАН. 1992. Т. 324. № 5. С. 953–958.
5. Koganov A.V. Processes and Automorphisms on Inductor
Spaces // Russian Journal Mathematic Physics. Vol. 4, № 3, 1996,
pp. 315–339.
УДК 519:522
МЕТОД ОПРЕДЕЛЕНИЯ РАЗМЫТОСТИ КОНТУРОВ
НА ЦИФРОВЫХ ИЗОБРАЖЕНИЯХ
П.П. Кольцов, к.ф.-м.н. (НИИСИ РАН, г. Москва, koltsov@niisi.msk.ru)
В работе предлагается метод оценки размытости изображения без привлечения априорной информации об условиях получения этого изображения. Метод основан на применении предложенного ранее оператора выделения линий, суть которого состоит в локальной аппроксимации фрагментов оцифрованного изображения другой, более простой функцией. Аппроксимация выполняется в окнах, форма которых приближена к круглой. В качестве простой
функции берется ступенчатая.
Ключевые слова: цифровое изображение, размытость, контур, яркость, искажение.
Трудности при обработке цифровых изображений в основном обусловлены помехами, главным образом, шумами различного происхождения
и недостаточной резкостью. В работах [1–3] с помощью тестирования были проведены сравнительные исследования реализаций наиболее популярных методов предобработки оцифрованных
изображений. Тестирование выполнялось по единой методике на одном и том же наборе специально сконструированных тестовых изображений, на
которые накладывались помехи различного типа и
уровня. На основе полученных результатов выработаны рекомендации по выбору наиболее подходящих для конкретных условий алгоритмов. Однако практическое применение этих рекомендаций затруднено из-за необходимости получения
количественной оценки уровня помех, в частности, степени расфокусировки, или размытости,
изображения, особенно при отсутствии информации об условиях, в которых происходило формирование изображения. В свою очередь, развитие
методов измерения размытости по самому изображению в отсутствие информации об условиях
получения изображения является нетривиальной
задачей, поскольку в реальной жизни мы имеем
дело с уже искаженными картинками и возможно38
сти прямого измерения искажений путем сравнения их с идеальными изображениями нет. В таких
условиях подобные измерения выполняются косвенно.
В настоящей работе предлагается метод оценки размытости оцифрованных изображений без
привлечения априорной информации об условиях
его получения.
Метод основан на применении оператора выделения линий [4, 5]. Суть его в локальной аппроксимации в выделенных окнах округлой формы фрагментов оцифрованного изображения другой, более простой ступенчатой функцией. В общем случае эта функция представляет собой три
ступеньки, разделенные двумя параллельными
прямыми. При этом крайние ступеньки соответствуют однородным областям с примерно одинаковой освещенностью, а полоса между ними – фрагменту разделяющей их линии. В частном случае,
когда между крайними однородными областями
существует четко выраженный перепад яркости,
ширина средней полосы может быть нулевой, то
есть аппроксимирующая функция будет представлять собой не три, а две ступеньки. Таким образом, данный оператор является обобщением оператора, предложенного в работе [6], в которой
Документ
Категория
Без категории
Просмотров
11
Размер файла
2 170 Кб
Теги
поле, моделирование, трехмерная, модуля, электронные, температурных
1/--страниц
Пожаловаться на содержимое документа