uzluga.ru
добавить свой файл


  • Разработаны математические и программные средства, позволяющие решать с использованием компьютера задачи по конструированию и исследованию 3D (многослойных) мелкозернистых структур. Эти средства объединены в технологию, названную клеточной. Составными частями технологии являются:

  • Модель клеточных вычислений, называемая Алгоритмом Параллельных Подстановок (АПП).

  • Методика синтеза параллельных архитектур, основанная на формальных и эвристических эквивалентных преобразованиях АПП.

  • Система имитационного моделирования параллельных вычислительных процессов, используемая для конструирования, отладки и получения характеристик моделей 3D мелкозернистых структур.

  • Технология обеспечивает отображение глубоко параллельного алгоритма решения задачи на архитектуру устройства с массовым пространственно-временных параллелизмом.

  • Ее основная особенность состоит в ориентации на построение моделей структур, состоящих из огромного коллектива достаточно простых вычислителей (клеток), имеющих преимущественно локальные связи и расположенных в трехмерном пространстве.


Парадигма клеточный автомат

  • Парадигма клеточный автомат

  • Перечень алгоритмов и структур

  • матричные и конвейерные

  • ассоциативные

  • вычислительные среды

  • универсальные клеточные

  • клеточно-нейронные сети

  • мультимикропроцессорные

  • Отличия от клеточного автомата

  • нарушение однородности клеточного пространства и локальности взаимодействия клеток

  • блочность структуры

  • широкий диапазон сложностей клеток

  • Сосредоточенное или распределенное управление взаимодействием блоков



Обрабатываемая информация задается в виде клеточного массива – множества клеток. Каждая клетка – это данное (бит, символ, число и т. д.) с приписанным «местом» нахождения в массиве.

  • Обрабатываемая информация задается в виде клеточного массива – множества клеток. Каждая клетка – это данное (бит, символ, число и т. д.) с приписанным «местом» нахождения в массиве.

  • Алгоритм задается множеством параллельных подстановок, имеющих левые и правые части. Выражение, стоящее в левой части подстановки для каждого имени клетки из перерабатываемого клеточного массива генерирует ассоциированный с этим именем клеточный массив и, если он содержится в перерабатываемом клеточном массиве, то подстановка выполняется. Ее выполнение означает, что некоторая, «базовая», часть найденного массива заменяется массивом, сгенерированным правой частью параллельной подстановки для того же самого имени клетки.

  • Процесс вычисления имеет итерационный характер: на каждом шаге выполняются все применимые в клеточном массиве параллельные подстановки. Вычисления заканчиваются тогда, когда к полученному на предыдущем шаге клеточному массиву не применима ни одна параллельная подстановка. Этот массив и есть результат работы АПП.



АПП соединяет в себе черты клеточного автомата и алгоритма Маркова.

  • АПП соединяет в себе черты клеточного автомата и алгоритма Маркова.

  • Базовые понятия: A – конечный алфавит, M – множество имен (не более чем счетное)

  • Клетка - пара (a, m), принадлежащая AM

  • Клеточный массив Wконечная совокупность клеток, в которой нет ни одной пары клеток с одинаковыми именами

  • Элементарная подстановка задается в виде , где W1, W2, W3 клеточные массивы

  • Результат применения подстановки к клеточному массиву W

  • Конфигурация , где , m – переменная в M,

  • множество именующих функций такое, что для

  • ,

  • Параллельная подстановка ,где S1, S2, S3 - конфигурации

  • применима к W, если существует непустое множество имен такое, что для всех

  • , .

  • Результат применения  к W:







Пример.

  • Пример.

  • АПП  сложения многих целых положительных двоичных чисел.

  • A={0, l}, M=N×N, W – это двумерная прямоугольная таблица, чьи клетки перенумерованы

  • парами чисел в соответствии с левой системой координат (i – абсцисса, j – ордината), m =

  • i, j. Разряды двоичных слагаемых расположены в строках таблицы, нижняя строка

  • нулевая, младшие разряды слагаемых занимают самый правый столбец таблицы. АПП 

  • состоит из двух параллельных подстановок:



































  • Понятия

  • У 2D (3D) АПП множество имен клеток - множество координат клеток двумерной (трехмерной) целочисленной решетки.

  • АПП интерпретируется сетью автоматов.

  • В сети, интерпретирующей 2D (3D) АПП, автоматы расположены в клетках решетки, которая образует двумерную (трехмерную) мелкозернистую структуру.

  • Преобразование 2D АПП в 3D АПП называется расслоением.

  • Предложены три способа расслоения:

  • расслоение, основанное на разделении на части команд подстановок;

  • расслоение, основанное на перестройке множества имен;

  • расслоение, основанное на разбиении исходного АПП на подалгоритмы.

  • Расслоения обеспечивают возможность дополнительной конвейеризации по третьему

  • измерению и вариант решения проблемы соединений в СБИС за счет перехода части

  • соединений в третье измерение и упрощения топологии слоя.











Вторая часть включает набор конструкций последовательного языка: средства описания процедур и функций (в том числе рекурсивных), блоков операторов, условных и параметрических циклов; опеpатopы yслoвия, выхoда из пoдпpoгpаммы, завеpшения пpoгpаммы и паyзы в испoлнении; oпеpатop пpисваивания и т.п. Основана на языке Pascal.

  • Вторая часть включает набор конструкций последовательного языка: средства описания процедур и функций (в том числе рекурсивных), блоков операторов, условных и параметрических циклов; опеpатopы yслoвия, выхoда из пoдпpoгpаммы, завеpшения пpoгpаммы и паyзы в испoлнении; oпеpатop пpисваивания и т.п. Основана на языке Pascal.

  • Третья часть отвечает за его расширяемость и содержит операторы import и use, с помощью которых в моделирующую программу можно осуществлять импорт внешних для системы библиотек, написанных как на языке системы, так и на языках С и С++.

  • Моделирующая программа состоит из главного программного блока, заключенного в операторные скобки begin - end., этот блок эквивалентен синхроблоку change - end. Главному блоку могут предшествовать вызовы библиотек, объявления глобальных переменных, тела функций и процедур.