Проблема трассировки и параллельно-последовательные D-алгоритмы на платформе механизма гипермассового параллелизма

Проблема трассировки и параллельно-последовательные D-алгоритмы на платформе механизма гипермассового параллелизма.

Д.т.н. Е.И. Артамонов, к.т.н. П.А. Правильщиков.

Почти всегда исчисления, алгоритмы вычислений и обработки информации, например, в виде перебора или выбора различных вариантов (вариантов путей или маршрутов, вариантов стоимости проекта или вариантов кодов для шифрования и дешифрования и т.п.) зависят от тех технических средств, которым располагает человек. Чтобы проиллюстрировать это сделаем короткий экскурс в историю вычислительной техники и напомним, что исчисление ― это совокупность правил оперирования с некоторым знаками (набором символов), позволяющая дать исчерпывающе точное описание некоторого класса задач, а для некоторых подклассов этого класса и описание алгоритмов их решения. Напомним также, что исчисление по-латыни звучит как «calculus», что в переводе означает «камешки». Почему? Оказывается, в качестве средств вычисления пастухи древнего Рима использовали при подсчёте овец камешки. У ворот овчарни было две лунки: левая и правая. При выгоне овец на пастбище, при выходе каждой овцы из ворот камешек из левой ямки перекладывался в правую. При загоне овец камешки из правой ямки перекладывались в левую. Если овца отсутствовала, то в правой ямке оставались камешки. По ним узнавали о пропаже.

    Позднее была создана десятичная система исчисления и арифметика, после чего были изобретены счёты. Способы вычисления на счётах отличаются от вычислений с помощью ка-мешков. Ещё позднее были разработаны механические калькуляторы, способы вычислений на которых совсем не похожи на способы вычислений на счётах и камешках. Британский учёный и изобретатель Ч. Бэббидж (1791 - 1871) одним из первых разработал проект универсальной механической вычислительной машины, в которой можно было использовать программы. Но создать такую машину в XIX веке Бэббиджу не удалось. Однако потребности в сложных вычислениях постоянно росли. Поэтому в XX веке для инженеров были созданы логарифмические линейки, для бухгалтеров электрические, а затем и электронные калькуляторы. Наконец, в 1945-46 годах XX века были созданы громоздкие ЭВМ (мейнфреймы), которые работали, последовательно выполняя команды той или иной программы. Но развитие средств и способов вычислений не остановилось: в начале 80-х годов мейнфреймы стали вытесняться настольными, а затем и мобильными ПК с одним процессором. ПК получили массовое распространение[1].
   Однако «эра, казалось бы, неограниченного роста производительности процессоров завершена: архитектуры на одном чипе не могут далее преодолевать ограничения на производительность, которые накладываются той энергией, которую они рассеивают и теплом, которое они выделяют. Сегодня Intel и другие полупроводниковые фирмы отказываются от модели с единственным быстрым процессором в пользу многоядерных микропроцессоров ― чипов, которые содержат два и более процессоров в одном корпусе» [1]. Так, постепенно начинается массовый переход на параллельные вычисления. Стремясь удовлетворить растущие аппетиты покупателей её продукции, корпорация Intel стала выпускать уже не двуядерные, а четырёхядерные процессоры[2].
    Переход на параллельные вычисления ведёт к революции в области вычислительной техники и математики. Эта революция не только сопоставима с той революцией, которая произо-шла при переходе от больших мейнфреймов к ПК, но может оказаться значительно глубже. Она может потребовать перестройки оснований математики и завершить окончательный переход от анализа бесконечно малых к дискретному анализу. В процессе этого перехода произойдёт окончательный отход от антропоморфных методов к новым «компьютероморфным» параллельно-последовательным алгоритмам вычислений: понадобятся исчисления, позволяющие «выжать» максимальное быстродействие из параллельных систем.

    В наши дни известны три механизма параллелизма: механизм общего параллелизма (не более 512 элементарных вычислительных модуля[3]), механизм массового параллелизма (от 1000 до 1 млн. элементарных вычислительных модулей) и механизм гипермассового параллелизма (более 1 млн.). В качестве элементарного вычислительного модуля в механизме общего и массового параллелизма выступает процессор, например, Pentium IV. Так, кластер Blue Gene, созданный IBM, состоит из 65 000 узлов, каждый из которых содержит два процессора (всего ― 130 тысяч процессоров). Наконец, стали коммерчески доступны системы с механизмом гипермассового параллелизма. В наши дни компания Olimpus Optical выпускает ДНК-компьютер. Он имеет молекулярную и электронную составляющую. В трёх см³молекулярной составляющей такого компьютера содержится около 100 триллионов молекул ДНК, каждая из которых является элементарным вычислительным модулем. Ещё большее число элементарных вычислительных модулей в виде отдельных атомов содержат квантовые компьютеры. В нескольких кубических сантиметрах их число достигает 10¹⁸. С помощью таких суперкомпьютеров уже удалось решить многие практические задачи, среди которых и одна из NP-полных задач ― задача о коммивояжёре. Эта задача решена с помощью ДНК-компьютера. Для авиакомпаний[4], чьи самолёты летают в сотни городов мира, эта задача имеет большое практическое значение, позволяя экономить горючее.
   При использовании таких экзотических суперкомпьютеров их сторонники часто говорят о производительности, о нанотехнологиях и их преимуществах, и увлекаясь, забывают об их недостатках[5]. Забывают они и о кремниевой интегральной технологии, достигшей высокой степени совершенства. Сегодня кремниевые технологии переходят к изготовлению БИС с технологической нормой в 65 нм. Недавно, инженеры Intel доказали, что кремниевая технология может создавать чипы, в которых технологические нормы не превышают 5 нм [2]. Возможно, в недалёком будущем технологические нормы кремниевых технологий удастся уменьшить до такой степени, что они окажутся вполне сопоставимыми по размерам и по быстродействию с легендарными углеродными нанотрубками [3]. Кремниевые технологии уже сейчас позволяют создавать системы с механизмом гипермассового параллелизма. Так, в [4] была предложена архитектура сопроцессора для ПК с механизмом гипермассового параллелизма. В качестве элементарного вычислительного модуля в таком сопроцессоре выступает блок пересечений. Число N_БПтаких блоков для 64 МБ активной оперативной памяти равно 512. Каждый блок реализует элементарную операцию a пересечения. Операция a является базовой операцией в исчисления кубических комплексов (ИКК) [5], которое используется при построении тестов в технической диагностике (ТД).
    Сразу же отметим, что в последнее время математические формализмы, разработанные и отработанные в рамках одной отрасли знаний часто переносятся в другую область науки, иногда достаточно далёкую от исходной. Так методы и алгоритмы ТД находят применение в других отраслях знания, например, в ихтиологии, в логистике и даже в физике [6-9]. Здесь же сделана попытка применения для решения проблемы трассировки печатных плат и БИС (в том числе и трёхмерных [10]) одного из таких формализмов: уже упомянутого ИКК.
   На основе этого исчисления строятся известные D-алгорит-мы [5]. Предлагаемое здесь решение проблемы трассировки является параллельно-последовательным решением и предлагаемые здесь D-алгоритмы являются параллельно-последова-тельными алгоритмами [4]. Эти алгоритмы «подогнаны» или, как иногда говорят, «заточены» под механизм гипермассового параллелизма на основе кремниевых технологий. Такие «заточенные» D-алгоритмы используются здесь не для построения тестов, как в [4], а для поиска оптимального (минимального по длине) маршрута от точки A до точки B в процессе трассировки печатной платы или БИС.

Постановка задачи трассировки хорошо известна (см., напри-мер, [11]–[13]). Для двумерного пространства (плоскости) тра-диционной планарной БИС или платы (например, квадратной платы с размерами l´s = 10´10 см ― рис. 1, а) требуется найти минимальный маршрут (или трассу) из точки A до точки B. Границы этой платы (или плоскости) образуют границы области трассировки. Если маршрут будет построен, то используя ту или иную технологий можно превратить в некоторый проводник. Задача затруднена тем, что в процессе построения маршрута могут встретиться препятствия ― тупики, связанные с областью запрета [12, стр. 152]. К ним относятся проведённые ранее проводники, размещённые активные, либо пассивные элементы и др. Например, на рис. 1,а показан уже проведённый проводник, пересекающий прямой отрезок, идущий из точки A в точку B. Но могут существовать и уже созданные проводники, которые должны быть включены в строящийся маршрут (см. рис. 1, где такой проводник показан розовым цветом)[6].
Для решения нашей задачи обычно используется сетка трассировки[7]. Но в нашем случае вся область трассировки разбивается на множество M дискретных площадок d_i,_j (çM ç = m), показанных на рис. 1,б. Площадки d_i,_j будем называть из дискретами. Здесь индексы i и j дискрета d_i,_j обозначают номера строк и столбцов соответственно по вертикали и по горизонтали (в системе координат XOY). Размеры дискрета d_i,_j подбирают инженеры-технологи с учётом доступной технологии. Инженер-технолог выбирает размер d_i,_j так, что в каждом дискрете может быть проложен проводник с соответствующим зазором для изоляции от соседнего проводника.
Рассмотрим, например, квадратную плату l´s = 10´10 см. Пусть нам доступна такая технология изготовления проводников на плате, когда дискрет с размером 1´1 мм оказывается вполне достаточным, чтобы в нём оказалось возможным «уло-жить» фрагмент проводника с учётом изолирующих расстояний от соседних проводников. Такой фрагмент проводника в одном дискрете позволяет осуществить трассировку маршрута, по которому будет проложен проводник с учётом изолирующих расстояний между соседними проводниками. Тогда можно подсчитать общее число m дискретов: m = 100´100 = 10000. В связи с таким, достаточно большим числом m здесь необходимо сделать важное замечание, касающееся примеров, которые будут приведены далее в статье. На рис. 1,б показано разбиение платы 10´10 см на 100 дискретов. Таким образом, один дискрет на этом рисунке составляет 1 см², а не один мм, как было сказано выше. В дальнейшем в целях иллюстрации предлагаемых нами параллельно-последовательных D-алго-ритмов для трассировки мы будем рассматривать плату, состоящую только из 100 дискретов (m = 100). Каждый дискрет может иметь площадь равную 1 см² или же 1 мм² или же ещё меньшую площадь. Для предлагаемых здесь параллельно-по-следовательных D-алгоритмов это не имеет значения. Важно лишь то, что объект трассировки (например, плоскость пла-ты) разбита на множество M (çM ç=m дискретов). Итак, нам удалось переформулировать «непрерывную» задачу в дискрет-ную. Теперь для решения нашей дискретной задачи следует перейти к созданию математической модели области трассировки. В качестве такой модели мы выберем логическую сеть [14]. С учётом особенностей проблемы трассировки специфика данной логической сети Cx, состоит в том, что Cx построена из множества K логических элементов типа «повтори-тель» (элемент «П») с одним входом и выходом. Любой проводник логической сети можно представить неограниченно большим множеством таких элементов «П». Активный элемент повторитель с атрибутом усиления действительно вставляют в длинные проводники в реальных БИС [10]. Здесь элемент «повторитель» используется только для того, чтобы заменить строящийся непрерывный маршрут для проводника некоторым дискретным маршрутом в логической сети. Этот маршрут будет строиться точно так, как строится по шагам виртуальным существенный путь в логической сети [4, 5].

В табл. 1 представлена таблица истинности элемента «П» с одним входом и одним выходом (рис. 2,б). Рядом в табл.2 приводится таблица D-кубов [9-12] этого элемента.

Таблица 1			Таблица 2
№	1	2	№	1	2
1	0	0	1	D	D
2	1	1	2	D’	D’

Теперь можно показать логическую сеть, состоящую из элементов «П», применительно к фрагменту дискретной платы (рис. 1,б) в окрестности точки A. Дискрет с точкой А окружают 8 дискретов. Следовательно, в данном случае логическая сеть имеет вид, показанный на рис. 3,а. На рис. 3,а все 8 дискретов в окрестности точки A (т.е. дискрета с точкой А) соответствуют выходам 9–16 восьми логических элементов «П» с номерами входов от 1 до 8-го. На рис. 3,б показана та же логическая сеть, но номера выходов элементов «П» соответствуют индексам восьми дискретов, окружающих дискрет d_2,2.

Таким образом, в процессе построения минимального марш-рута каждый элемент «П» будет соответствовать переходу от одного дискрета к другому. Вследствие наличия тупиков переход от одного дискрета к другому может быть удачным или неудачным (тупик). Удачный переход будет означать появлением символа D на выходе элемента «П» и, следовательно, в том дискрете, который соответствует выходу данного элемента. Неудачный ― символом Æ (символом пустого множества).Для нашего фрагмента в окрестности дискрета с точкой A на всех выходах 8 элементов «П» появятся символы D, так как в процессе построения все переходы оказываются удачными ― см. табл. 2 и рис. 3.Теперь, после того, как создана математическая модель платы (или БИС) в виде логической сети, то остальное дело техники, т.е. техники использования ИКК и последовательных или параллельно-по-следовательных D-алгоритмов [4, 5].
В заключение подчеркнём, что использование параллельно-последователь-ных D-алгоритмов позволяет осуществлять одновременное построение всех существенных путей (D-цепей) в логической сети [4]. Это и позволяет выбрать из них маршрут .

Литература.

1. Hennessy J., Patterson D. Computer Architecture. A Quantitaive Approach. (Fourth Edition), Morgan Kaufmann, 2006, 406 p.
2. Попов М. Февральская буржуазная революция.
// КОМПЬЮТЕРРА, 2005, № 9 (581). С. 44.
3. Hiramoto M. Saitoh I, and Tsutsui G.. Emerging nanoscale silicon devices taking advantage of nanostructure physics. // IBM Jour-nal of Research and Development, 2006. Vol. 50, № 3. P. 411-418
4.. Правильщиков П.А. Закон сохранения перебора и естественный параллелизм D-алгоритмов для построения тестов и моделирования в технической диагностике. // Автоматика и телемеханика, 2004, № 7. Стр. 156-199.

5. Roth J.P. Diagnosis of automata failures: a calculus and method.
// IBM Journal of Research and Development. 1966, № 7. P. 18-32.
6. Гольдман В.Р., Чипулис В.П. Диагностические методы определения координат мест сезонного сбора косяков в Охотском море в целях оптимизации промышленного вылова рыбы. // А и Т. 1973,
№ 10. Стр. 133-146.
7. Чипулис В.П. Диагностирование утечек в гидравлических
цепях (I). //Автоматика и телемеханика, № 1, 1997г. Стр. 150-159.

8. Правильщиков П.А. «Физическая» теорема Нётер в фотонике и computer science. (I). // Прикладная физика, 2005, № 6. С. 82- 98.

9. Правильщиков П.А. «Физическая» теорема Нётер в фотонике и computer science. (II). //Прикладная физика, 2006, № 1. С. 37- 46.

10. Topol W. and all Three-dimensional integrated circuits. //IBM Jour-nal of Research and Development, 2006. Vol. 50, № 3.
P. 491-506.
11. Артамонов Е.И., Ромакин В.А., Сизова Л.Н., Тенякшев А.М. Автоматизированное проектирование и выпуск схемной документации на аппаратуру средств связи. Методическое пособие. МТУСИ. Москва. 2005г. 25 стр.
12. Сучков Д.И. Проектирование печатных плат в САПР P-CAD 4.5―CAD 8.5 и ACCEL EDA. М.: Малип, 1997. ― 576 с.

13. Разевиг В.Д. ACCEL EDA ― P-CAD для Windows // PC Week/RE, № 20, 996. С.41-43.
14. Карибский В.В., Пархоменко П.П., Согомонян Е.С., Халчев В.Ф. Основы технической диагностики.
Кн. 1, М.:"Энергия", 1976, 346 с.

[1] В 2005 г. было произведено около 200 млн. ПК.

[2] В ноябре должен выйти четырёхпроцессорный Core 2 Extreme QX6700 с частотой 2,66 ГГц. Он будет совместим с материнскими платами на базе набора системной логики Intel 975X. (См. Компьютеры и оргтехника, 2006, № 28 (305), стр. 7)

[3] Иногда это число увеличивают до 1000.

[4] То есть задача об оптимальном маршруте для самолётов авиакомпаний.

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

[6] Для трёхмерных БИС (3D БИС) такие проводники могут, например, быть использованы для создания вертикальной архитектуры, т.е. создания связей между различными слоями 3D БИС.

[7] Напомним, что под сеткой трассировки понимается однородная система вертикальных и горизонтальных прямых линий, по которым могут проводиться трассы в процессе автоматической трассировки соединений. Расстояние между ближайшими вертикальными и горизонтальными линиями одинаково по всей сетке и называется шагом сетки. Сетка трассировки может располагаться по всей печатной плате или занимать её часть [12].