Содержание к диссертации
Введение
ГЛАВА I. Система АЛЛ-ПС 10
I. Организация системы 10
2. Управление памятью 23
3. Системное окружение 33
4. Файловая система 40
5. Интерактивный редактор 43
ГЛАВА II. Срэдства обработки изображений и язык образ 48
I. Основные характеристики 49
2. Типы данных 56
3. Структуры 62
4. Операции 67
5. Определяемые функции 97
ГЛАВА III. Параллельная реализация 103
1. Обзор методов и подходов 103
2. Систегшая модель вычисления. 106
3. Систегшая реализация 109
4. Уровни параллелизма НО
Заключение 116
Литература
Управление памятью
Основная память в системе АІШ-ПС делится на два уровня. Первый - оперативная память ЭВМ СМ-2, второй - память процессорных элементов ПС-2000. В такой интерактивной среде, как АЛЛ, непрерывно возникает потребность в основной памяти, например: для хранения странслированной программы пользователя во внутреннем виде; значительный размер памяти должен быть отведен системным программам, которые производят вспомогательные действия при выполнении програглгл пользователя; память под определяемые пользователем структуры данных и константы; временная память для хранения промежуточных результатов при вычислении выражений; если в выражении рекурсивные вызовы подпрограмм, то для хранения частичных результатов на каждом уровне рекурсии может потребоваться потенциально неограниченное число временных переменных и т.д.
Существуют и широко применяются несколько методов распределения пагшти, ошісашше в [24]. Рассмотрим распределение пагшти на уровне основной пагшти ОЗУ СМ-2. При выборе управления. пагшти в системе АПЛ-ПС надо было проделать следующую работу.
Первое - выбрать определенную стратегию и, соответственно, алгоритмы распределения памяти, подходящие для системы; второе - реализовать выбранную стратегию, оставляя широкие возможности для ее модификации в ходе экспериментов.
Выбор стратегии распределения памяти Внутреннее представление разбиения пагшти. Представим себе текущее состояние некоторой области пагшти. Она состоит из совокупности "занятых" (не используемых) и "свободных" блоков.
Сразу же возникают первоочередные проблемы: а) каким образом такое разбиение памяти представить в машине; б) каким алгоритмом для поиска блока из N последовательных свободных ячеек следует воспользоваться. Ответ на первый вопрос не вызывает сомнений: следует где-то хранить список свободного пространства. Чаще всего для этого наиболее целесообразно использовать само свободное пространство. Таким образом, мы можем связать между собой свободные сегменты, например, через первое слово каждой свободной области. Свободные блоки можно "связать" между собой в порядке увеличения или уменьшения их размера, либо в порядке адресов памяти, либо в совершенно случайном порядке.
Что касается вопроса б), то, очевидно, если необходимы № последовательных слов, мы должны найти свободный блок, в котором содержится М М слов и уменьшить его размер до M-W (если пе К=М , то блок следует исключить из списка свободных). Монет случиться, что есть несколько блоков, содержащих N или более слов, и тогда возникает вопрос: какой из них следует предпочесть?
Рассмотрим две широко распространенные стратегии. .
Стратегия типа "первый подходящий" и "наилучший подходящий". По стратегии типа "наилучший подходящий" выбирают ту область, в которой И ячеек, где И - наименьшее из существующих значении, равных или больших fi . Обычно здесь требуется просмотреть весь список свободного пространства, прежде чем сделать выбор. По стратегии типа "первый подходящий" берется первая встретившаяся область, в которой слов.
Стратегия "первый подходящий" - быстрая стратегия, но интуитивно видно, что она расходует большие блоки, преждевременно распределяя их части. Стратегия "наиболее подходящий" оставляет большие блоют для использования в будущем, но является более медленной, она также имеет тенденцию создавать много маленьких и бесполезных дыр, что обычно нежелательно. Примеры двух стратегий приведены на рис.
Эксперименты с обоими этими методами в широком диапазоне моделируемых данных были выполнены Кнутом [25]. В большинстве случаев система со стратегией "наилучший подходящий" прекращает работу раньше (тупик) из-за недостаточности памяти.
Метод "первый подходящий" при поиске доступного пространства монет быть ускорен с помощью простого приема [26].Предположим, что данные о блоке (размер и адрес) хранятся в списке. Прямой поиск мог бы всегда начинаться с вершины списка и продолжаться последовательно, пока не будет найден подходящий блок памяти. К сокаленига, это ведет к концентрации меньших блоков вблизи начала списка, поэтому с течением времени требуется все больше и больше времени для нахогццения подходящего блока.
Эффективная схема, которая бы обеспечивала более равномерное распределеіше размера по списку, заключается в том, чтобы начинать поиск в некоторой переменной точке 0- внутри списка. Одна из возмонностей для указания Q состоит в том, чтобы при успешном поиске назначать Q следующий номер за выбранным блоком памяти.
Файловая система
Поэтому для решения задач, имеющих дело с обработкой больших объемов данных, на распределенной пшшти в системе АПЛ-ПС создана файловая система.
Под файлом понимается именованная область, куда можно помещать данные таким образом, чтобы они были доступны программам из рабочей области, но не занимали место в этой области.
Так же как и рабочие области, файлы имеют игле на. Единица данных, хранящаяся в файле, имеет такую же структуру, как и переменная, хранящаяся в рабочей области. Однако, в отличие от данных, расположенных в рабочей области, доступ к которым осуществляется по именам, данные, хранящиеся в файлах, отыскиваются по номерам, которыми снабжены единицы данных в файле. Отдельная единица данных в файле называется компонентой (в противоположность переменной). Сам файл состоит из последовательности таких компонент.
Создание и открытие юайла. Для создания и открытия файлов слупит двухместная функция tOPW. Левым параметром является вектор, состоящий из двух компонент. Первая компонента - тип файла, вторая - длина файла в секторах. Первая компонента определяет АЛЛ - или АСПО - формат файла. Она необходима для того, чтобы работать с данными, полученными программами на других языках (Фортран, Алгол, Бейсик и т.д.), а такие с данными в формате АПЛ-системы. Вторая компонента - длина файла -монет быть опущена, если файл упе существует, иначе, создается файл на диске с начальной длиной, равной второй когшоненте. Правым параметром является имя создаваемого (открываемого) файла, оно монет быть расширено указанием порядкового номера диска, на котором находится открываемый файл, например: А О 0 500 0PW ПРИМЕР::20.
В результате этой команды на 20 диске (порядковый номер) будет создан файл с именем "ПРИМЕР" размером 500 секторов в АШГ-аюрмате.
Результатом работы функции будет логический номер открытого файла, который занесется в переменную А. По этому номеру мопно обращаться к файлу, когда файл находится в активном состоянии (открытый). Предпочтительнее пользоваться номером файла, а не его именем, так как, если открыто несколько файлов одновременно, то имеется возможность перейти от одного файла к другому, используя номер как индекс.
Доступ к Файлу. Для чтения информации из файла используется одноместная функция ttG-ET. Функция считывает в активную рабочую область копии запрашиваемых компонент, хранящихся в файле. Чтение файла не меняет его содержимого. Параметром функции является вектор, состоящий из двух компонент, первая -номер файла, вторая - номер записи в файле, которую надо считать. Вторая компонента монет отсутствовать, тогда вчитывается текущая запись файла и указатель на текущую запись увеличивается на единицу. Для записи данных в файл слупит двухместная функция &PUT , Левым параметром является номер активного файла, правыгл - данное, которое надо поместить в файл.
Закрытие шайла. Одноместная функция #CLZ служит для закрытия файла. Параметром функции является логический номер активного файла. функция # CLZ производит следующие действия: - закрывает файл на диске; - освобождает логический номер; - освобождает элемент таблицы активных файлов.
Для обеспечения возможности именования и хранения алгоритмов для их многократного использования под соответствующими именами и с необходимыми аргументами системе ІШЛ-ЇЇС был необходим свой редактор. Необходимость иметь "свой собственный редактор" обусловлена тем, что часто при выполнении каких-либо вычислений возникает потребность внести изменения в уже существующие или создать новые програмш-функции, не теряя при этом полученных промежуточных результатов, т.е. "не выходя" из системы. Для этого и был создан интерактивный редактор, в состав которого входят простые, но вполне достаточные для удобного редактирования, команды.
Исходным файлом для редакции является символьный файл функции, результатом работы редактора является оттранслированная, функция, которая записывается в рабочую область пользователя.
Команды редактирования подразделяются на команды построчного редактирования, которые позволяют: - вводить текст; - выставлять текст в уже существующий файл; - исключать строки; - заменять строки;
Структуры
Векторы. Векторы состоят из компонент, обладающих одинаковыми свойствами: либо только из чисел, либо только из символов. При подсчете компонент вектора символов необходимо учитывать, что символ (кавычка) представляется двумя идущими подряд кавычками. Котшонепты векторов нутлеруются слева направо.
Тип вектора (числовой, символьный) определяется его синтаксисом. Подтип числового вектора (вещественный, целый, логический) определяется путем анализа его компонент. Если все компоненты числового вектора 0 или I, то он логический. Если вектор содержит хотя бы одну вещественную компоненту, то вещественный, иначе - целый.
Особую роль в языке играют векторы со.значением пусто. Пустой вектор символов имеет вид пусто . Пустой вектор чисел и вектор чисел из одной компоненты явно не задаются, а являются результатами некоторых функций. Пустые векторы используются для вывода на терминал пустой строїш, для определения переменной со значением пусто и в операторе ветвления. Синтаксис векторов приведен в приложении 15.
Массивы. Массив - это совокупность элементов, с каждым из которых связан упорядоченный набор целых чисел, называемых индексами. Набор индексов определяет однозначно элемент совокупности (частным видом массива является матрица, позиция элемента матрицы описывается двутш индексаїли). Число индексов массива определит его число.измерений. Массив с N индексами называют Ь/ -мерным (N/=0,1,...). Каждый индекс изменяется с постоянным шагом от начального до конечного значения. Число значений индекса одного измерения называют длиной или размерностью измерения.
В языке начальные значения индексов массивов начинаются с I. Полное описание структуры массива дается его вектором размерностей. Каждая компонента этого вектора является размерностью одного измерения массива: первая - первого измерения, вторая - второго и т.д. Очевидно, что число элементов массива равно произведению компонент его вектора размерностей. Например, если массив X имеет вектор размерностей 3 4, то это значит, что X является матрицей (двумерным массивом) из трех строк и четырех столбцов.
Если вектор размерностей массива содержит хотя бы одну нулевую компоненту, то соответствующий массив пустой. Вектором размерностей пустого вектора является числовой вектор из одной нулевой компоненты. Многомерные массивы строятся из элементарных данных одного и того не типа. Подтип числового массива (вещественный, целый, логический) определяется либо путем анализа подтипов его компонент, как, например, в случае вектора чисел, либо функцией, которая его создает.
При описании процесса выполнения программы говорят, что некоторые синтаксические конструкции обладают значением. В ОБРЛЗе основной конструкцией является выражение, поэтому целесообразно расстлотреть связь между некоторнші выражениями и их значениями. Значения любого выражения рассматриваются как массив:
I). Значением скаляра является массив с нулевым числом измерений. Его тип определяется типом скаляра. Его вектор размерностей - пустой числовой вектор;
2). Значением вектора является одномерный массив, сформированный из.компонент вектора. Тип значения определяется типом вектора. Вектор размерностей значения - числовой вектор из одной компоненты, которая указывает число компонент исходного вектора;
3). Многомерные массивы формируются в результате выполнения некоторых функций языка. В обращениях к этим функциям прягло или косвенно указывается вектор размерностей создаваемого массива и исходный массив, из компонент которого формируется результирующий массив. Тип создаваемого массива определяется типом компонент исходного массива.
Таким образом, в языке ОБРАЗ значение - это массив. Оно включает в себя признак.типа, вектор размерностей и совокупность компонент массива.
Язык содержит широкий набор функций для обработки массивов как единых объектов. Это значит, что выполнение каждой функции может рассматриваться как ее одновременное (параллельное) применение к каждой компоненте массива в отдельности, если функция унарная, или к каждой паре соответствующих компонент двух массивов-аргументов в отдельности, если функция бинарная.
Систегшая модель вычисления.
Разнообразие форм организации параллельных вычислений отражает различную проблемную ориентацию в использовании таких вычислений, разные критерии оценки их эффективности, неоднозначные пути при достижении определенных целей. В связи с этим возникают вопросы, с одной стороны, об адекватности архитектурных моделей и языковых средств реальным задачам обработки информации, а с другой - о разработке таких методов параллельных вычислений, которые бы эффективно "погружались" в программно-аппаратные средства тех или иных вычислительных систем [34].
При создании традиционных, последовательных методов таких вопросов возникает значительно меньше, так как разработчик, как правило, опирается на архитектуру.вычислительной системы, состоящей из процессора и памяти, т.е. архитектуру, в значительной мере отражающую понятие алгоритма. При создании методов, ориентированных на параллельные вычисления, их разработчикам необходимы также канонизированные модели отражающие определенные архитектурные гипотезы и позволяющие абстрагироваться от свойств конкретных вычислительных систем.
Для определения канонизированной модели параллельных вычислений, которую могшо использовать при создании методов параллельной обработки информации, необходшло выбрать достаточно общую гипотезу об архитектуре многопроцессорной вычислительной системы. В настоящее время выделяются два основных подхода при выборе таких гипотез.
Первый связан с идеальными моде лягли вычислительных систем; в таких моделях предполагается, что число процессоров не ограничено пли достаточно большое, работают процессоры над общей одноуровневой памятью, все они одновременно могут выполнять операции и при этом не существует конфликтов по доступу к одним и тем ке данным. Такие модели в большинстве случаев не могут быть реализованы на практике, однако их использование позволяет оценить сложность алгоритмов, выявлять предельные возможности распараллеливания задач, новые методы организации вычислений [54].
Второй подход связан с реальными моделями вычислительных систем, т.е. моделями, в которых число процессоров ограничено, память имеет несколько уровней иерархии, время различных операций различно, существуют конфликты по доступу к памяти, необходимы дополнительные действия для синхронизации процессоров и т.п. [55,56,57,52,58,70]. Реальные модели, в свою очередь, могло разбить на ряд подклассов в зависимости от предполагаемых методов доступа к памяти, способов синхронизации процессов, возможности совмещения счета с обменами данными и т.п. [34].
Каждое данное в модели имеет свой описатель (дескриптор), в котором хранится информация о типе, структуре и месте расположения данного. Дескриптор может быть отделен от данного, а данные, в свою очередь, могут находиться на разных уровнях памяти.(внешняя память, оперативная память в разных процессорах). Раздельное хранение описания и самого данного позволяет использовать разные функции для обработки структуры и самого данного
Функции в модели разделяются на вычислительные и интерфейсные. К вычислительным относятся арифметические, тригонометрические и т.п. функции, выполняющие операции над скалярами и массивами. Вычислительная функция является примитивной , так как в ней нет вызовов других функций. Она обладает такой важной характеристикой, как обработка количества информации в единицу времени. При использовании этой характеристики имеется возможность вводить синхронные процессы на системном уровне, напршлер, составляя расписания для наиболее полной и равномерной загрузки процессоров и т.п. Каждая вычислительная функция может обрабатывать данные, которые находятся в ее области определения (в оперативной памяти соответствующего процессора). Перепись данных из одной области в другую осуществляют интерфейсные функции.
В режиме считывания и записи интерфейсные и вычислительные функции могут работать одновременно над разными данными, над одинаковыми - только в режиме считывания. Напршлер, если запрос на изменение данного еще не выполнен, то последующие запросы к этому данному будут ожидать выполнения записи в данное, несмотря на их готовность к выполнению.
