Файл: Оперативные графические системы в автоматизации проектирования..pdf

Г л а в а 6

ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В ПРОЕКТИРУЕМОМ ОБЪЕКТЕ В ЭВМ

Взаимодействие инженера-проектировщика с ЭВМ в оперативных графических системах ведется на привыч­ ном для него языке чертежей, графиков, схем, рисунков. Такой режим обмена человека с ЭВМ предполагает особую организацию памяти для записи и хранения дан­ ных (модели технического объекта). Элементы данных (идентификаторы, цифровые величины, коды, символы) размещаются в памяти в определенном порядке таким образом, что определяются ассоциативные связи, суще­ ствующие между ними и отражающие отношения различ­ ных компонентов реального объекта. Такая организация (структура) данных (с.д.) должна удовлетворять ряду требований, выдвигаемых ОГС:

данные должны быть организованы таким образом, чтобы имелась возможность идентифицировать все объекты, обладающие одинаковыми свойствами;

структура данных должна обладать большой сте­ пенью динамизма, позволяя включать и исключать элементы данных произвольным образом;

структура данных должна обеспечить формирова­ ние образов из отдельных элементов и изменение их при изменении элементов;

поиск и выбор родственных элементов из с.д. должен проводиться достаточно эффективно.

В процессе проектирования часто встречаются опера­ ции типа добавить или стереть элементы, масшабирование картинки, геометрические преобразования изобра­ жения. Все эти операции требуют значительных измене­ ний в с.д., которая должна позволить проводить все эти изменения достаточно быстро.

160

Следует подчеркнуть, что требования, налагаемые на с.д., а следовательно, и реализация самой с. д. в значи­ тельной степени определяются конкретным применением графической системы. Сложность структуры данных за­ висит от характера взаимосвязей элементов объекта, требуемого времени реакции ОГС, объема памяти для хранения структуры и т. д.

Основной проблемой, которая возникает при разра­ ботке с.д., удовлетворяющей поставленным требова­ ниям, является разрешение двух противоречий — затра­ ты минимального объема памяти для хранения с.д. и увеличения скорости обработки ее. Так, компактное раз­ мещение данных требует для некоторых операций боль­ шого времени поиска элементов. И наоборот, время об­ работки структуры с дополнительным количеством свя­ зей и признаков может быть значительно уменьшено.

При рассмотрении различных типов с.д. основное внимание необходимо уделить определению с.д., пред­ ставлению с.д. в оперативной памяти ЭВМ, распределе­ нию памяти для хранения с.д., обработке с.д.

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

Все известные разновидности организаций данных могут быть представлены тремя основными структурами: последовательной, произвольной и списочной [1].

6.1. ПОСЛЕДОВАТЕЛЬНАЯ СТРУКТУРА ДАННЫХ

Простейшей организацией данных является последо­ вательная структура, в которой логический порядок свя­ зи элементов структуры соответствует физическому по­ рядку размещения этих элементов в памяти. Так, для представления одномерного массива целых чисел в памя­ ти необходимо первое, второе, третье... числа разместить в последовательные ячейки. Последовательная структура часто применяется для организации массива команд ото­ бражения. При этом в последовательные ячейки памя­ ти записываются как графические команды, так и коман­ ды управления. При использовании такой организации

любое изменение изображения требует перестроения все­ го массива.

Распределение памяти при последовательной органи­ зации данных может быть как статическим, так и дина­ мическим. При статшческом распределении заранее ре­ зервируется участок памяти, требуемый для хранения данных. В том случае если размеры массивов заранее не

Рис. 6.1. Динамическое распределение памяти при последовательной организации данных: а — начальное состояние; б — выполнение про­ граммы В1; в — передача управления программе В2; г — окончание выполнения программы В2

известны, то приходится отводить для каждого массива максимально необходимое ему количество ячеек в па­ мяти.

При динамическом распределении память отводится при входе в блок данных, а при выходе из блока — осво­ бождается. В качестве примера динамического распреде­ ления памяти рассмотрим магазинное распределение па­ мяти, реализованное в трансляторе с языка АЛГОЛ60 [2]. После загрузки программы остающаяся часть памяти используется для образования магазина, причем адрес первой свободной ячейки магазина запоминается в специальной ячейке (указателе магазина) (рис. 6.1, а). При выполнении программы с некоторого блока В1 он размещается в начале магазина, а указатель изменяется (рис. 6.1, б). Когда блок В1 передает управление новому блоку В2, занимается участок памяти над блоком В1 и происходит изменение указателя (рис. 6.1, в). При выхо­

162

де из блока В2 указатель принимает предыдущее значе­ ние (рис. 6.1, г). Таким образом, участок памяти, требуе­ мый для размещения данных, можно представить как эпизодически наращиваемый и укорачиваемый с одного конца массив. Такая схема распределения памяти оказы­ вается достаточно эффективной в языке АЛГОЛ 60, в ко­ тором принят блочный принцип построения программ П'Р'Н этом выход из одного блока, выполнение которого не завершилось к началу выполнения другого, не может быть сделав раньше выхода из второго блока. Этот прин­ цип исключает появление «щелей» в магазине, т. е. чере­ дования свободных участков памяти с занятыми.

Поиск элементов последовательной структуры может быть осуществлен достаточно быстро, однако включение нового элемента или стирание старого в структуре с упо­ рядоченными по каким-то признакам элементами требует изменения всей структуры каждый раз при внесении в нее изменений. По этой причине последовательная орга­ низация данных не используется в качестве основной структуры в оперативных графических системах.

6.2. ПРОИЗВОЛЬНАЯ СТРУКТУРА ДАННЫХ

Произвольная организация данных основывается на установлении связи между идентификатором элемента и адресом памяти, по которому записывается данный эле­ мент. Определение соответствия между идентификато­ ром и адресом можно вести двумя методами: с помощью таблиц, кодированием по идентификатору.

Метод организации таблиц (словарей). Этот метод находит широкое применение для формирования таблиц при трансляции программ. В таблице записываются идентификаторы элементов и адреса ячеек, в которых размещены сами элементы (рис. 6.2). Однако в случае большой с.д. размер таблицы увеличивается, что приво­ дит к значительному времени поиска адреса элемента, а следовательно, и самого элемента. В случае организации таблицы с размещением идентификаторов в определен­ ном порядке время поиска элемента сокращается, но при этом после каждого изменения в таблице ее следует упорядюччивать, что требует также значительного времени. По этой причине этот метод не находит широкого приме­ нения в оперативных графических системах.

Метод кодирования по идентификатору. В данном методе используется значение самого элемента пли его идентификатора для размещения элемента в памяти. Для вычисления адреса в таблице, куда следует поместить элемент с данным идентификатором, необходимо произ­ вести различные преобразования над идентификатором

(рис. 6.3). Нанлучшими преобразованиями считаются такие, которые позволяют для каждого идентификатора вычислить единственный адрес. В том случае, если два различных идентификатора дали один и тот же адрес, необходимо предусмотреть метод разрешения этого про­ тиворечия, так как по одному адресу в таблицу должен быть записан только один элемент.

Алгоритмы вычисления адресов. Существует несколь­ ко алгоритмов вычисления адреса по идентификатору [3]. Если идентификатор состоит из А бит, то вычислен­ ный адрес размером в а бит (причем а < А ) используется

164

как индексная величина для адресации любого элемента в таблице.

Наибольшее распространение получил алгоритм с использованием умножения. Для получения адреса код идентификатора возводится в квадрат или умножается на постоянную величину, и из середины полученной ве­ личины выбирается а бит. Так как значение средних бит квадрата зависит от всех А бит идентификатора, можно

ИДЕНТИФИКАТОР

ТАБЛИЦА

ЭЛЕМЕНТОВ

ИДЕНТИФИКАТОР ЭЛЕМЕНТЫ

Рис. 6.3. Кодирование по идентификатору при произвольной струк­ туре данных

предполагать, что различные идентификаторы с большей степенью вероятности дадут различные адреса даже в том случае, если совпадают их начальные или конечные биты. В качестве примера определим адрес, получаемый в результате вычислений производимых над идентифика­ тором ПРЯМ1. Если все цифры от 0 до 9 закодировать величинами 0—9, а символы А, Б, В, ..., Я — величинами 10, 11, .... 43 соответственно, то идентификатор ПРЯМ1, расположенный в памяти последовательно символ за символом, можно представить в следующем виде:

ПРЯМ1

2723432401,

165

Затем сложим все значения величин, определяющих символы и цифры, и получим код идентификатора 123. Умножая код идентификатора иа постоянную величину (например, 4) и выбирая четыре средних бита, получим адрес в таблице а — 14.

Во втором алгоритме используется деление, при этом в качестве адреса берется остаток от деления идентифи­ катора на величину, определяющую размер таблицы.

В третьем алгоритме (логическом) определенная часть бит идентификатора выделяется с помощью опера­ ции булевой алгебры (II, ИЛИ и т. д.).

Однако все эти алгоритмы не дают однозначного соот­ ветствия идентификаторов и вычисленных адресов. Два различных идентификатора могут дать один и тот же ад­ рес. Так, при логическом алгоритме вычисления адресов

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

Методы формирования таблицы элементов при «столкновениях». Предложено н используется много ме­ тодов, разрешающих противоречие, которое возникает

166

при получении одинакового адреса пр,п преобразовании двух разных идентификаторов [4].

Псевдослучайный метод предусматривает использо­ вание генератора псевдослучайных чисел. Метод заклю­ чается в следующем:

1. Вычисляется адрес в таблице по одному из возмож­ ных алгоритмов преобразования идентификатора.

2. Если по адресу / расположен элемент с данным идентификатором или ячейка свободна, то выполняется операция чтения элемента из таблицы или запись в сво­ бодную ячейку нового элемента.

3. Если по адресу / расположен элемент с другим идентификатором, то следует обращение к генератору псевдослучайных величин, который выдает целое число р. Тогда дополнительный адрес будет равен /+ р п совер­ шается переход к п. 2.

генератор выдал все числа, таблица считается заполнен­ ной п включить новый элемент в нее оказывается невоз­ можным. Важным свойством этого метода является малое число «столкновений» в результате вычисления до­ полнительного адреса р. Если два элемента с первона­ чальными адресами а и b в каком-либо шаге дадут оди­ наковый адрес, т. е. а-]-р; = й+ р/, при некоторых i и /г, то

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

167