Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова

УДК 681.3

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Організація паралельних процесів у спеціалізованих обчислювальних системах з ортогональним доступом до пам'яті

05.13.13 - обчислювальні машини, системи та мережі

Душеба Валентина Віталіївна

Київ 2001

Загальна характеристика роботи

Актуальність роботи. Підвищення продуктивності обробки даних продовжує залишатися одним з основних вимог до обчислювальних систем, які проектуються, що зумовлює необхідність використання високошвидкісних елементів на базі розвитку нових технологій; організації паралельних обчислень і створення багатопроцесорних систем при максимальній відповідності топологічної структури системи структурі алгоритмів, що виконуються.

Однією з відмінних особливостей багатопроцесорної обчислювальної системи (БОС) є мережа обміну, за допомогою якої процесори з'єднуються один з одним або з пам'яттю. Модель обміну настільки важлива для багатопроцесорної системи, що багато які характеристики продуктивності та інші оцінки визначаються відношенням часу обробки до часу обміну, відповідних задач, що вирішуються. Існують дві основні моделі міжпроцесорного обміну: одна заснована на передачі повідомлень, інша - на використанні загальної пам'яті.

Кожний процес повинен виключати для всіх інших процесів можливість одночасного з ним звернення до спільних даних (взаємовиключення). Коли процес звертається до даних, що розділяються, вважається, що він знаходиться в своїй критичній ділянці. Для забезпечення узгодженості даних і синхронізації процесів в архітектурі із загальною (що розділяється) пам'яттю частіше за все використовуються стандартні методи операційної системи, такі як семафори або блокування процесів. Такі традиційні засоби сильно ускладнюють процес програмування і саму процедуру синхронізації.

В архітектурах з розподіленою або віртуальною пам'яттю, що розділяється, узгоджений стан пам'яті забезпечує система обміну повідомленнями. Однак процедура формування блокуючих або неблокуючих повідомлень із заголовками впливає відчутним чином на зниження продуктивності моделі обміну і всієї системи загалом.

При оцінці будь-якого механізму обміну критичними є три характеристики продуктивності: смуга пропущення, затримка та приховування затримки. У ідеалі затримка повинна бути настільки мала, наскільки це можливе. Для її визначення критичні накладні витрати апаратури і програмного забезпечення, пов'язані з ініціюванням і завершенням обміну. Ефективність приховування затримки залежить від того, наскільки добре механізм приховує затримку шляхом перекриття обміну з обчисленнями або з іншими обмінами.

Часто, і притому необгрунтовано, в машинах із загальною пам'яттю і векторних машинах витрати на обмін не враховуються, оскільки ці проблеми значною мірою приховані від програміста. Однак накладні витрати на обмін в цих машинах є, і вони визначаються конфліктами шин, пам'яті і процесорів. Крім того, бажано, щоб як можна менший об'єм даних пересилався між процесорами, оскільки комунікаційні операції є значно більш повільними, ніж обчислення.

Проблеми мінімізації складності керування обчислювальним процесом можуть бути вирішені шляхом функціональної орієнтації апаратного і програмного забезпечення, а розширення локальної підмножини задач забезпечується за рахунок моделювання властивостей реконфігурації міжмодульних зв'язків і функцій окремого модуля.

На основі вищевикладеного можна зробити висновок про актуальність розробки таких методів організації паралельних обчислювальних процесів і міжмодульного обміну даними в БОС, які забезпечують зростання продуктивності і зниження програмної складності системи, але не супроводяться збільшенням апаратної і структурної складності.

Мета і задачі дослідження. Метою роботи є розробка методів організації взаємодії паралельних обчислювальних процесів в багатопроцесорних обчислювальних системах з ортогональним доступом до пам'яті, що дозволяють мінімізувати витрати корисного комп'ютерного часу.

Основні задачі, що визначаються поставленою метою:

? аналіз особливостей організації взаємозв'язків паралельних обчислювальних процесів і їх синхронізації в БОС та обгрунтування основних принципів організації безконфліктного міжмодульного обміну;

? синтез узагальненої математичної моделі локальної підмножини задач на основі аналізу часткових математичних моделей для рішення систем рівнянь;

? розробка методів організації адресного простору пам'яті і синхронізації паралельних обчислень для ортогональних структур;

? розробка структурної організації ортогональних багатопроцесорних обчислювальних систем.

Об'єктом дослідження є багатопроцесорні обчислювальні системи з ортогональним доступом до пам'яті.

Предметом дослідження є організація взаємодії паралельних обчислювальних процесів на основі використання нових принципів обміну.

Метод дослідження. У ході дослідження використовується математичний апарат теорії моделювання, чисельних методів, теорії графів, теорії обчислювальних систем, теорії алгоритмів і теорії множин.

Наукова новизна одержаних результатів полягає в наступному:

? запропонований підхід до побудови узагальненої математичної моделі на основі синтезу часткових математичних моделей локальної підмножини задач, що дозволяє відобразити топологію обчислювального процесу і самої структури;

? сформульовані принципи міжпроцесорного обміну в багатопроцесорній системі, що покладено в основу створення нового підходу в концепції інформаційного обміну;

? запропонований новий метод міжпроцесорного обміну, який дозволяє зменшити складність програмних засобів синхронізації та забезпечення безконфліктності обмінних процесів;

? запропонований метод розшарування адресного простору пам'яті, що дозволяє створити модель узгодженого (когерентного) стану пам'яті;

? запропонована організація ортогональних багатопроцесорних обчислювальних систем з розшаруванням і переключенням, що забезпечують узгодження взаємодії паралельних гілок програми на кожному ітераційному кроці.

Практичне значення одержаних результатів. Практична цінність роботи складається в наступному:

? розроблений порядок виконання адресних арифметико-логічних команд, який забезпечує можливість їх одночасного використання як команд обміну і знижує складність програмної процедури обміну;

? розроблена методологія синтезу часткових математичних моделей певного класу задач на прикладі рішення систем лінійних алгебраїчних і диференційних рівнянь та приведення вихідної задачі до єдиної операційної форми;

? розроблені структури ортогональних багатопроцесорних обчислювальних систем з переключенням і розшаруванням, призначених для реалізації паралельних алгоритмів;

? розроблена структура узгодженої пари буферів пам'яті, які перемикаються, що дозволяє зняти обмеження на клас задач, які вирішуються в ортогональних обчислювальних системах.

Результати дисертаційної роботи впроваджені в Організації, яка заінтересована у розробці ефективних методів організації взаємодії паралельних процесів у спеціалізованих обчислювальних системах і використовуються в учбовому процесі на кафедрі комп'ютеризованих систем захисту інформації Національного авіаційного університету.

Зв'язок роботи з науковими програмами, планами, темами. Одержані результати дисертаційної роботи реалізовані в рамках: Державної науково-технічної програми “Перспективні засоби обчислювальної техніки і елементи інфраструктури інформатизації" напряму 05.03.01/006К-95 по темі 06.03.01/024-92 “Ортогональна багатопроцесорна система", зареєстрованої в ДКНТ України за № UA01001737P; НДР “Розробка нових ефективних методів обміну даними в системах моделювання" - № гос. реєстрації 0197U014997, ДНТП шифр 1.9.2.6.

Особистий внесок здобувача. У роботах, написаних в співавторстві, автору належать: дослідження і аналіз спільності характеристик моделей локальної підмножини задач, синтез узагальненої математичної моделі і розробка методу організації пам'яті проблемно-орієнтованої системи [1, 6 - 12]; дослідження особливостей міжпроцесорного обміну і його синхронізації в БОС, обгрунтування принципів міжпроцесорного обміну [2]; дослідження особливостей ортогонального доступу до пам'яті і розробка методів організації адресного простору пам'яті з розшаруванням і переключенням [3, 4]; реалізація та експериментальні дослідження функціонування узгодженої пари буферів пам'яті [5].

Апробація результатів дисертації. Основні положення дисертаційної роботи і результати наукових досліджень представлялися і обговорювалися на: другій республіканській науково-технічній конференції “Функционально ориентированные вычислительные системы" - ФОВС-II (Харків, 1990); всесоюзній науково-технічній конференції “Математическое моделирование в энергетике" - ЭНМО-90 (Київ, 1990); III міжнародній науково-технічній конференції “Методы управления системной эффективностью функционирования электрифицированных и пилотажно-навигационных комплексов” - Авионика-95 (Київ, 1995); міжнародному міжрегіональному семінарі Наукової Ради НАН України “Технічні засоби захисту інформації" (Київ, 2000-2001); науковому семінарі кафедри інформаційно-діагностичних систем Національного авіаційного університету (Київ, 2000); щорічних науково-технічних конференціях і наукових семінарах, що проводяться в ІПМЕ НАН України (Київ, 1990-2001);.

Публікації. Основні положення і результати дисертації відображені в 12 публікаціях, з них 5 статей у наукових фахових журналах.

Структура і об'єм дисертації. Робота складається з вступу, чотирьох розділів, висновків, списку використаних джерел, містить 24 рисунка, 10 таблиць. Загальний обсяг дисертації становить 127 сторінок.

Основний зміст роботи

У вступі дано обгрунтування актуальності роботи, формулюється мета дослідження і визначаються задачі для її реалізації, відзначені новизна і практичне значення одержаних результатів.

У першому розділі проводиться дослідження систем паралельної обробки даних і аналіз існуючих моделей обміну. Дається огляд різних схем класифікації багатопроцесорних систем, головними вимогами до яких є: можливість класифікації як існуючих, так і передбачуваних багатопроцесорних систем; диференціація істотно різних багатопроцесорних систем; однозначна класифікація будь-якої багатопроцесорної системи. Проводиться аналіз основних характеристик і класифікаційних ознак багатопроцесорних обчислювальних систем, розглядається можливість побудови класифікації, яка б досить повно відображала всі системи та їх особливості. Найбільш прийнятною є багаторівнева відкрита класифікація, що дозволяє вносити нові структурні вирішення обчислювальних систем.

Ставиться задача дослідження і визначення класу відомих методів і алгоритмів розв'язання різних задач, на прикладі вирішення систем лінійних алгебраїчних і диференційних рівнянь, з точки зору можливості виділення деяких єдиних якісних характеристик та створення узагальненої форми представлення певного класу методів, як єдиної мови, що описує, з іншого боку, основні принципи побудови спеціалізованих обчислювальних модулів системи і що відображає їх склад.

Суть такого підходу складається в представленні вихідної математичної моделі у вигляді деякої сукупності операцій, об'єднаних у формі узагальненої операційної моделі, з подальшим набором обчислювальної структури з процесорних модулів, що реалізують вибрану макрооперацію. З метою ж мінімізації програмної складності, керування обчислювальним процесом може здійснюватися на рівні формування пакету інформаційно-керуючих коефіцієнтів, що входять до складу загальної моделі.

Досліджується роль операційної системи (ОС) у багатопроцесорних системах з множинним потоком команд в області міжпроцесорного обміну. Відомо, що в таких системах кожна паралельна гілка програми представляється у вигляді відносно автономного обчислювального процесу, а всі взаємодії між такими процесами керуються операційною системою, яка виступає в цьому випадку як загальносистемний ресурс.

Розглядаються основні недоліки універсальних механізмів обміну. Так для конвеєрних систем, у разі використання концепції процесів, кожна ступінь системи повинна (в ідеальному випадку) на початку і в кінці кожного циклу роботи ступені звертатися до операційної системи: перший раз для зчитування даних з попередньої ступені, а другий - для запису даних в наступну ступінь. Причому, таке звертання буде відбуватися одночасно з іншими ступенями системи, в той час як операційна система має можливість обслуговувати ці звертання тільки послідовно, що вступає в суперечність з можливостями ОС як загальносистемного ресурсу. Тоді час роботи i-ї ступені можна визначити як:

t_i = t_ci + nt_osi + f(n),

де t_ci - чистий час роботи кожної ступені; t_osi - час обслуговування ступені операційною системою на кожному циклі роботи системи; n - число ступенів конвеєра; f(n) - витрати часу всередині ОС, непрямо пов'язані з обслуговуванням ступенів і зростаючі із зростанням числа процесів, що обслуговуються. З цього слідує, що: існує деяке граничне значення n, збільшення числа ступенів вище за яке призведе до зменшення продуктивності системи; використання системи для програм з обсягом обчислень нижче деякого мінімального значення є неефективним. Мінімізація часу, що витрачається ОС на обслуговування взаємодії процесів дозволить збільшити продуктивність обчислювальної системи загалом.

Конкуренція процесів через відсутність системних ресурсів, обумовлює появу тупиків і приводить до необхідності розробки механізмів по їх запобіганню. Основні труднощі при використанні як шин, так і комутаційних схем спричиняє режим переривань, з яким пов'язаний міжпроцесорний обмін. При цьому, крім істотного зниження продуктивності системи виникають і інші непрості проблеми: програмування обробки переривань в кожному з процесорів системи і автоматичне розпаралелювання програми.

Таким чином, окреслене коло проблем, спрощення і вирішення яких складається в максимально повному виключенні арбітражу міжпроцесорного обміну з боку операційної системи.

У другому розділі обгрунтовано новий підхід до організації міжпроцесорного обміну в багатопроцесорних обчислювальних системах. Для порівняльної оцінки вводиться поняття ідеального міжпроцесорного обміну.

Нехай є об'єктний код А деякої програми для процесора конкретного типу, який складається з n паралельних фрагментів

А =,

де A_i - i-й паралельний фрагмент програми.

При розв'язанні даної програми на n-процесорній системі, що складається з процесорів аналогічного типу, кожний паралельний фрагмент A_i може бути реалізований на окремому процесорі за умови, що буде включена додаткова програмна процедура S_i, на яку покладається здійснення всіх функцій, пов'язаних з міжпроцесорним обміном. Процедура S_i - це фрагмент зв'язку. Наявність фрагментів зв'язку, специфічних для кожного типу систем, призводить до значного зниження основних експлуатаційних характеристик системи.

Ідеальним міжпроцесорним обміном вважається обмін, який здійснюється без участі фрагментів зв'язку, а сумарна сукупність інструкцій, що виконуються розпаралеленої програми, при цьому не відрізняється від сукупності інструкцій нерозпаралеленої програми.

Зменшення продуктивності обчислювальної системи пов'язане з простоями окремих процесорів через неможливість їх рівномірного завантаження, а також з витратами корисної обчислювальної потужності системи на реалізацію всіх додаткових процедур, спричинених розпаралелюванням. Як правило, типова процедура асинхронного обміну складається з трьох стадій. На першій стадії проводиться аналіз ознак, що знаходить відображення в операціях аналізу значень семафорів. На другій стадії здійснюється власне обмін. На третій стадії відбувається установка ознак, або на мовному рівні здійснюється модифікація семафорів.

Перша і третя стадії програмної процедури обміну не тільки можуть бути замінені апаратною процедурою, але й допускають поєднання у часі з власне обміном. Таким чином, на здійснення цих стадій не витрачається корисний комп'ютерний час.

Друга стадія використовує звернення до оперативного запам'ятовуючого пристрою (ОЗП) за операндом за допомогою адресних арифметико-логічних операцій. Існує можливість організувати пам'ять багатопроцесорної системи таким чином, щоб звернення до неї за допомогою адресних команд при деяких умовах було у той же час і міжпроцесорним обміном. Причому, кожне звернення до такої пам'яті буде мати відповідне йому звернення до ОЗП у нерозпаралеленій програмі.

Режим очікування процесора при ідеальному обміні необхідно здійснювати без команди умовного переходу. Можливим способом реалізації такого підходу є вплив на тривалість синхроімпульсу процесора.

Сформульовані принципи міжпроцесорного обміну в багатопроцесорній системі:

1. Два довільних процесори системи Р(i) і Р(i+1) взаємодіють тільки через буфер пам'яті m(i) і жоден з них не формує керуючих сигналів для іншого.

2. Звернення до буфера пам'яті (БП) може здійснюватися будь-якою адресною арифметико-логічною операцією (а не командами введення-виведення).

3. Підключений до процесора буфер пам'яті є частиною його ОЗП і перекривається його адресним простором.

4. Обидва процесори Р(i) та Р(i+1) можуть звертатися до буфера m(i) асинхронно і без попереднього програмного аналізу його стану.

5. Кожен із процесорів забезпечений програмним механізмом передачі відповідного буфера пам'яті суміжному процесору і не має механізму його захоплення.

6. Буфер пам'яті завжди підключений тільки до одного з процесорів і не має нейтрального непідключеного стану.

7. Звертання процесора до буфера пам'яті в момент часу, коли він підключений до суміжного процесора, переводить його в режим очікування.

Визначені особливості виконання адресних команд, які складаються в наступному:

? паралельно з виконанням адресної команди, при якому відбувається звернення до БП, здійснюється апаратний аналіз стану буфера пам'яті;

? якщо буфер пам'яті підключений до процесора, то виконання адресної операції не має відмінностей від типової операції звернення до пам'яті;

? якщо буфер пам'яті відключений від процесора, виробляється сигнал, по якому затягується у часі початковий синхроімпульс процесора і блокується формування сигналу вибірки даного порту БП;

? керуючим впливом, що ініціює апаратний аналіз стану буфера пам'яті, є сигнал вибірки БП, що формується в процесі дешифрації адресу, що і дозволяє використати один і той же набір адресних команд процесора як для звернення до локальної пам'яті, так і для звернення до буфера пам'яті;

Команда умовного переходу для організації режиму очікування, таким чином, не використовується.

Схема взаємодії процесора Р(i) і сполучених з ним модулів пам'яті m(i-1) і m(i), які в початковому стані підключені відповідно до процесорів Р(i-1) та Р(i) представлена на рис. 1.

Рис. 1. Схема взаємодії процесора Р(i) з сполученими модулями пам'яті m(i-1) та m(i)

ортогональний доступ обчислювальна система

Зв'язок здійснюється за допомогою шин адресу і даних AD1, AD2. Кожний буфер пам'яті має в своєму складі двопортову пам'ять DM і семафорний модуль SP, а процесор складається з пристрою обробки інформації CD і формувача синхроімпульсів CLK. При цьому мається на увазі, що арифметико-логічний пристрій, пристрій керування, пам'ять програм і даних і пристрій введення-виведення розташовані в пристрої обробки інформації. У підході, що пропонується на структурну організацію пристрою обробки інформації не накладається практично ніяких обмежень.

Зроблено аналіз рівня паралелізму базового алгоритму обчислювального процесу. Розглянуто порядок розпаралелювання алгоритму розв'язання задач.

Розглянута організація пам'яті процесора ортогональної багатопроцесорної системи, структурна схема якої містить процесори Р(1), Р(2), ... , Р(n) і квадратну матрицю розмірності n² буферів пам'яті. Довільний процесор Р(i) може мати доступ лише до i-о стовпця або до i-о рядка матриці буферів пам'яті. Дисципліни такого доступу різні, але основними є розшарування адресного простору процесора і переключення.

Як оперативний запам'ятовуючий пристрій процесора Р(i) можуть виступати i-й рядок та i-й стовпець матриці буферів пам'яті. Це означає, що звернення до чарунок такого ОЗП здійснюється за допомогою адресних команд процесора. Внаслідок того, що буфери пам'яті M_ij і M_ji будуть входити до складу ОЗП процесорів Р(i) та Р(j), вони можуть бути використані для здійснення обміну між названими процесорами.

Таким чином, пропонується як команду обміну використати будь-яку адресну арифметико-логічну операцію. При цьому кожний буфер пам'яті, зв'язаний з даним процесором, використовується для обміну даними з певним процесором системи і для цих цілей відводиться постійний фіксований діапазон адресного простору.

Крім того, запропоновано систему кодування, яка дозволяє здійснити перехід від процесора до адреси і назад. Для цього кожному процесору системи присвоюється абсолютний номер, відповідний його порядковому номеру в системі (наприклад, процесор системи Р(i) має абсолютний номер i). Процесори також мають внутрішню нумерацію, на базі якій будується відповідна система адресації. При такому підході певний процесор системи буде записуватися в адресних частинах інших процесорів різними адресними кодами.

Відносний номер n_ij процесора Р(j) в системі нумерації процесора Р(i) визначається із співвідношення:

Оскільки системи, що досліджуються допускають використання будь-якої адресації, в роботі розглядаються особливості формату адресної команди процесора, виходячи з специфіки міжпроцесорного обміну, на прикладі прямої адресації.

У слові довжиною N біт (р+n+1) молодших розрядів відведені під адресну частину команди. Старші розряди слова, призначені для коду інструкції, не розглядаються.

Оперативна пам'ять процесора складається з двох частин різного функціонального призначення. Перша (локальна пам'ять) - призначена для зберігання програм і даних; другу складають буфери пам'яті, зв'язані з даним процесором. Для збільшення ємності локальної пам'яті використовують розподілення адресного простору на два рівних діапазони. Перший діапазон призначений для звернення до буферів пам'яті, другий - до локальної пам'яті. При такому розподіленні "одиниця" в старшому (р+n)-у розряді адреси служить ознакою звернення до локальної пам'яті процесора, "нуль" - до буферів пам'яті.

Щоб зробити можливою запис одного й того ж операнда однією командою в певну чарунку відразу декількох або всіх буферів пам'яті, зв'язаних з даним процесором, адресний простір процесора розшаровується по відношенню до операцій з циклом запису та з циклом читання.

При записі операнда i-м процесором системи в буфери пам'яті i-о рядка (стовпця) матриці адресна частина команди визначається із співвідношення:

де - номер чарунки буферів, в які записується операнд.

При читанні операнда i-м процесором з чарунки з номером буфера пам'яті M_ji адресна частина команди визначається співвідношенням:

A_ij = +2^P (n_ij-1) .

Синхронізація роботи паралельної програми здійснюється адресними арифметико-логічними операціями обміну. Якщо операнд використовується одночасно в декількох паралельних гілках, то його копії формуються і напрямляються безпосередньо в кожну гілку програми. Це більш раціональне, ніж засилати його в загальну пам'ять, добування з якої, як і саме засилання будуть пов'язані з великими процедурними витратами (конфліктами, чергами, тупиками і т.п.)

Буфер пам'яті передається програмно сполученому процесору, що володіє програмно-апаратним механізмом такої передачі, але що не має механізму захоплення буфера. Для процесора має значення саме підключення (або не підключення) до нього буфера пам'яті. Якщо буфер підключений, то в ньому у відповідних чарунках є необхідна в даний момент інформація. Тому звернення до буфера здійснюється без попередньої перевірки наявності відповідної інформації.

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

У третьому розділі розглянуті питання структурної організації ортогональних багатопроцесорних систем, а також кардинального спрощення процедури міжпроцесорного обміну і його синхронізації.

Запропонований метод організації ортогональної багатопроцесорної системи з розшаруванням (ОБСР). Система має матричну структуру і містить процесори Р(1), Р(2), ... , Р(n), n*(n-1) буферів пам'яті та два загальносистемних елементи "И". Довільний процесор Р(i) має можливість доступу для запису інформації в БП M_i1, M_i2, ... , M_in відповідного рядка матриці і читання з БП M_1i, M_2i, ... , M_ni відповідного стовпця. Структурна схема ОБСР представлена на рис. 2.

Рис. 2. Структурна схема ортогональної багатопроцесорної системи з розшаруванням

Якщо в i-у процесорі системи відбувається обчислення m_i правих частин системи рівнянь, для яких в загальному випадку необхідно використати значення невідомих, отриманих на попередній ітерації іншими процесорами, то запис обчислених компонент в буфери пам'яті здійснюється відповідно до запропонованої схеми матричної структури розмірності nn. На k-й ітерації процесор Р(i) за адресою m_i-1 всіх буферів пам'яті i-о рядка матриці запише -ю компоненту вектора. У цьому випадку кожний стовпець матриці буферів буде містити всю множину компонент шуканого вектора.

У загальному випадку m_i m_j, отже час, що витрачається процесорами на кожну ітерацію, буде різним. Це вимагає певної дисципліни когерентності процесів запису і читання компонент вектора в БП. У запропонованій схемі вона зводиться до слідуючого: 1) ніякий процесор системи не може почати читання компоненти на черговій ітерації, якщо в системі є хоч би один процесор, який не здійснив запис навіть однієї компоненти вектора у відповідні буфери пам'яті на попередній ітерації; 2) ніякий процесор системи не може почати запис обчисленої компоненти на черговій ітерації, якщо в системі є хоч би один процесор, який ще не прочитав хоч би одну з призначених йому компонент вектора.

Тимчасовий цикл обчислень на кожній ітерації складається з двох тимчасових інтервалів, в першому з яких процесори можуть здійснювати тільки запис обчислених компонент, а у другому - тільки їх зчитування.

Для здійснення згаданої дисципліни доступу в набір команд кожного процесора вводяться дві синхронізуючі команди SET W і SET R, а в систему - два елементи "И". Команда SET R інформує систему про завершення процесором операцій читання з відповідних БП і готовності почати запис компонент, що виконуються знову. На апаратному рівні ця процедура відповідає установці процесором сигналу "Системне читання завершене" (СЧЗ) одиничного рівня на відповідному вході першого елемента "И".

Оскільки немає ніякої іншої синхронізуючої процедури, процесор після виконання оператора продовжує роботу відповідно до програми, але його спроба звернутися до БП для запису обчисленої компоненти може перевести його в режим очікування, який здійснюється апаратними методами і не має програмного виразу. У цьому випадку починається виконання адресної операції запису, але її цикл затягується у часі до моменту закінчення читання всіма процесорами відповідних компонент. Після виконання команди SET R всіма процесорами системи, на виході першого елемента "И" формується загальносистемний сигнал "Дозвіл системного запису" (ДСЗ) одиничного рівня, який дає дозвіл на запис обчислених компонент в БП всім процесорам системи і на завершення вже початих операцій запису.

Аналогічно, після завершення запису всіх обчислених компонент вектора у відповідний рядок БП, кожний процесор оповіщає систему, виконавши команду SET W, про завершення операцій запису компонент, формуванням сигналу "Системний запис завершений" (СЗЗ) одиничного рівня, встановивши його на відповідний вхід другого елемента "И". Після завершення операцій запису всіма процесорами системи на виході другого елемента "И" формується загальносистемний сигнал "Дозвіл системного читання" (ДСЧ) одиничного рівня, що дозволяє читання обчислених компонент із БП.

Реалізація розглянутого способу обміну пред'являє до процесора додаткові вимоги, які включають формування сигналів СЧЗ і СЗЗ та прийом і формування відгуків на загальносистемні сигнали ДСЗ і ДСЧ. У роботі детально описана структурна організація процесора для ортогональних багатопроцесорних систем з розшаруванням і його основні функціональні вузли.

Запропоновано метод організації ортогональної багатопроцесорної системи з переключенням (ОБСП). У склад ОБСП, структурна схема якої представлена на рис. 3, входять процесори Р(1), Р(2), ... , Р(n), n² буферів пам'яті і один загальносистемний елемент "И".



Рис. 3. Структурна схема ортогональної багатопроцесорної системи з переключенням

Метод міжпроцесорного обміну, що реалізується в рамках другої структурної організації, заснований на поперемінному переключенні стовпців буферів пам'яті на рядки і зворотно. У початковому стані до кожного i-о процесора системи підключено i-й рядок матриці буферів пам'яті, в який процесор має доступ як для запису, так і для зчитування інформації.

Нехай непарну (2k+1)-у ітерацію знаходження коріння системи рівнянь процесор Р(i) починає при наявності всіх компонент вектора X в i-у рядку матриці БП. При цьому довільний буфер i-й рядка M_ij містить складову вектора X_j = {}. У процесі обчислень на 2k+1-й ітерації процесор Р(i) заносить у всі БП i-о рядка матриці компоненти тільки однієї складової вектора X_i = {} таким чином, що компонента x_f(i)+1 виявляється записаною в нульові чарунки всіх БП i-о рядка матриці, компонента x_f(i)+2 - в перші чарунки буферів пам'яті і т.д.

Виконанням інструкції POST кожний процесор інформує систему про завершення запису обчислених ним компонент. На апаратному рівні це виражається в формуванні сигналу "Кінець циклу процесора" одиничного рівня і установці його на відповідному даному процесору вході загальносистемного елемента "И", на виході якого, після виконання оператора POST всіма процесорами системи, формується сигнал "Кінець циклу системи", по якому здійснюється переключення рядків буферів пам'яті на відповідні стовпці і навпаки.

Наступну парну ітерацію i-й процесор починає з підключеним до нього i-м стовпцем буферів пам'яті і набором всіх компонент шуканого вектора, записаного в даний стовпець всіма процесорами системи на першій ітерації.

Таким чином, на всіх непарних ітераціях до процесорів підключені рядки буферів пам'яті, а на парних - стовпці. На кожній непарній 2k-1-й ітерації процесор записує компоненти вектора X у всі n буферів пам'яті i-о стовпця матриці, а на кожній парній 2k ітерації - у всі n буферів пам'яті i-о рядка матриці.

Стан системи, коли один з її процесорів має доступ до рядка, а інший, в той же самий момент, до стовпця матриці БП, є забороненим, що дає можливість використати один і той же діапазон адресного простору як для звернення до стовпця, так і для звернення до рядка матриці.

Чи буде мати місце звернення до стовпця або рядка при деякому фіксованому значенні адреси, залежить від стану системи. Для звернення до l-ї чарунки буферів пам'яті M_ij та M_ji i-й процесор системи оперує одним і тим же значенням адресної частини команди. Внаслідок такої симетрії немає необхідності окремо програмувати звернення до рядків і стовпців матриці. З позицій програмування це є зверненням до масиву фіксованої довжини, під який відведений фіксований діапазон адресного простору, а процес переключення рядків і стовпців залишається невидимим для програміста.

Розглянуті додаткові вимоги до процесора, що накладаються на нього особливостями обміну в ОБСП, які зводяться до необхідності в програмному формуванні сигналу "Кінець циклу процесора" і відгуку на загальносистемний сигнал "Кінець циклу системи". Розроблена докладна структурна схема процесора і його основних функціональних вузлів.

У четвертому розділі зроблено порівняльний аналіз систем, що проектуються, результати якого зведені в табл. 1 і 2. В таблицях приведені результати оцінки рішення системи лінійних алгебраїчних рівнянь (порядку 832) на ОБСР, ОБСП і системі класу ОКМД для різних ступенів регулярності матриці коефіцієнтів. Всі системи складаються з 52 процесорів, ємність буферів пам'яті в ортогональних багатопроцесорних системах 16 слів.

Табл. 1 дає оцінки для системи з повною матрицею коефіцієнтів, а табл. 2 для системи, в якій кожний рядок матриці коефіцієнтів має 30% випадковим образом вибраних нульових коефіцієнтів.

Таблиця 1

Клас БОС	Коефіцієнт ідеальності I	Коефіцієнт прискорення S52
ОБСР	0,949	49,47
ОБСП	0,9999687	51,998
ОКМД	1,0	52

Таблиця 2

Клас БОС	Коефіцієнт ідеальності I	Коефіцієнт прискорення S52
ОБСР	0,927	48,46
ОБСП	0,9999553	51,998
ОКМД	0,7	36,4

Наведені оцінки показують, що системи класу ОКМД є ефективним інструментом реалізації "ідеальних систем", але непіддатлива обліку на них нерегулярність матриці різко знижує їх ефективність. Показник S визначається величиною середнього прискорення обчислень на однопроцесорній системі по відношенню до n-процесорної системи, а коефіцієнт ідеальності I - кількістю додаткових команд, спричинених розпаралелюванням програми в ортогональних системах або пустих, спричинених нерегулярністю матриці коефіцієнтів в системах класу ОКМД, та кількістю команд в нерозпаралеленій програмі.

Розроблений і запропонований досить універсальний спосіб міжпроцесорного обміну, який дозволяє зняти будь-які обмеження на клас задач, що вирішуються в ортогональних багатопроцесорних обчислювальних системах, на базі якого можна створювати багатопроцесорні системи різних класів і які відображаються будь-якими структурними графами.

Принципова відмінність підходу, що пропонується від відомих полягає в тому, що переключення буферів не є функція загальносистемного арбітру, по сигналу якого воно здійснюється, а є прерогативою взаємодіючих процесорів системи. При цьому будь-яка довільна пара процесорів системи Р(i) і Р(j) може програмно обмінюватися, зв'язаними з ними буферами пам'яті M_ij та M_ji.

У початковому стані буфери M_ij і M_ji підключені відповідно до процесорів Р(i) та Р(j), кожний з яких накопичує в своєму буфері масив операндів для іншого. Як тільки накопичення масиву завершене, процесор спеціальною командою відключає від себе заповнений буфер. Таку процедуру відключення буфера повинен здійснити і інший процесор. Причому, немає ніякої необхідності в якомусь узгодженні між процесорами в цих процедурах відключення. По завершенні цієї пари відключеннь в самих буферах формується локальний сигнал, по якому відбувається фізичне переключення цієї пари буферів. Загалом в процесі обчислень кожний з цієї пари процесорів повинен видати однакове число операцій відключення на згадану пару буферів, в іншому випадку станеться зупинка системи. При цьому, процесори не мають механізму захоплення буферів і, отже, повністю відсутня всяка конкуренція при міжпроцесорному обміні.

При такій дисципліні доступу до буферів пам'яті будь-який довільний процесор системи Р(i) в кожний довільний момент часу може мати доступ до m буферів i-о рядка та l буферів i-о стовпця матриці, причому, в процесі функціонування системи кожне з чисел l і m може приймати будь-які значення з множини {1, 2,..., n}, при цьому завжди m+ln.

Звертання процесора Р(i) до k-ї чарунки будь-якого буфера пам'яті, з пари буферів M_ij і M_ji, відбувається за допомогою однієї й тієї ж фіксованої адреси, тобто виконуючи операції обміну, процесор не знає, до якої саме з цієї пари буферів в даний момент він звертається. У цьому випадку процесору важливо своєчасно виконувати операцію відключення, після якої він може почати працювати тільки з новим буфером пам'яті. Якщо операнд, що обчислюється процесором використовується в декількох паралельних гілках програми, то він однією командою запису надсилається в кожний з відповідних процесорів, вказаних в її адресній частині. Доцільно, щоб і команда відключення буферів допускала відключення відразу декількох або всіх буферів зв'язаних з даним процесором.

З переключенням буфера змінюється і його нумерація, тобто до процесора Р(i) завжди підключений буфер M_ij незважаючи на періодичну змінюваність фізичних буферів. Крім того, для здійснення фізичного переключення в кожний буфер пам'яті вводиться додаткова логіка, що забезпечує відключення буфера по команді POST А, в адресній частині якої закодований номер даного буфера. Внаслідок того, що фізичне переключення буферів пам'яті M_ij і M_ji здійснюється синхронно, кожна така пара буферів повинна мати синхронізуючий зв'язок.

Для пари буферів пам'яті такого типу вводиться поняття узгодженої пари. Загальне число узгоджених пар h в системі визначається виразом h=n(n-1)/2. У пари не входять тільки буфери пам'яті, розташовані по діагоналі матриці, незалученні у міжпроцесорний обмін і введені тільки для виключення додаткових пересилок операндів всередині відповідних процесорів.

У критичному інтервалі завжди існує імовірність того, що процесор повторно звернеться до узгодженої пари. У цьому випадку він переходить в режим очікування в процесі виконання даної адресної інструкції. Всі сигнали для реалізації механізму очікування формуються, на відміну від розглянутих систем, у відповідному буфері пам'яті.

У даному підході спрощення програмної процедури міжпроцесорного обміну знижує програмну складність багатопроцесорної системи і крім істотного збільшення продуктивності системи приводить до кардинального спрощення технології програмування, включаючи автоматизацію розпаралелювання програм, для такого класу систем. Збільшення структурної складності при цьому буде вельми незначним.

Проведені експериментальні дослідження на моделюючому стенді, підтвердили достовірність теоретичних положень роботи.

Висновки

У дисертаційній роботі наведене теоретичне обгрунтування і нове вирішення наукової задачі організації взаємодії паралельних обчислювальних процесів в багатопроцесорних обчислювальних системах з ортогональним доступом до пам'яті, що забезпечує скорочення витрат корисного комп'ютерного часу і дозволяє будувати системи, що відображаються різними структурними графами.

У ході роботи отримані наступні результати:

Запропоновано і розроблено підхід до побудови узагальненої математичної моделі на основі синтезу часткових математичних моделей локальної підмножини задач (на прикладі рішення систем лінійних алгебраїчних і диференційних рівнянь), що дозволяє відобразити топологію обчислювального процесу і самої структури.

На основі аналізу традиційних механізмів обміну, теоретичних і прикладних аспектів проблеми, що досліджується, сформульовані принципи міжпроцесорного обміну і його синхронізації, що стало основою для створення нового підходу в концепції інформаційного обміну в багатопроцесорній системі.

Запропоновано новий метод міжпроцесорного обміну, який відрізняється розробленим порядком виконання адресних арифметико-логічних операцій, що забезпечує можливість їх одночасного використання як операції обміну і дозволяє зменшити складність програмних засобів синхронізації та забезпечення безконфліктності обмінних процесів.

Запропоновано метод розподілу адресного простору пам'яті, де кожному процесору відводиться фіксований діапазон адресного простору з розшаруванням по відношенню до операцій з циклом запису і циклом читання, що дозволяє створити модель узгодженого (когерентного) стану пам'яті.

Розроблено механізм синхронізації міжпроцесорного обміну в спеціалізованих обчислювальних системах з ортогональним доступом до пам'яті для ефективного несуперечливого функціонування і взаємодії паралельних гілок програми.

Запропоновано методи структурної організації ортогональних багатопроцесорних обчислювальних систем з розшаруванням і переключенням, орієнтовані на реалізацію алгоритмів, які вимагають узгодження взаємодії паралельних гілок програми на кожному ітераційному кроці.

Розроблена, виготовлена і експериментально досліджена на моделюючому стенді система двох спеціальним чином організованих двопортових буферів пам'яті, використання яких в ортогональних багатопроцесорних системах знімає обмеження на клас задач, що вирішуються, і дозволяє будувати системи, які відображаються будь-яким структурним графом. Достовірність теоретичних положень, викладених в роботі, підтверджується результатами, отриманими в ході експерименту.

Публікації по темі дисертації

1. Пивень Н.Ю., Чернышев Ю.Ю., Душеба В.В. Об одном подходе к проектированию СВС // Гибридные вычислительные системы и комплексы. - 1988. - 11. - С. 45 - 49.

2. Сигарев А.А., Душеба В.В. Организация многопроцессорных систем класса МКОД // Электронное моделирование. - 1999. - 21, № 1. - С. 47-57.

3. Сигарев А.А., Душеба В.В. Методы организации ортогональных многопроцессорных систем. I // Электронное моделирование. - 1999. - 21, № 4. - С. 57-65.

4. Сигарев А.А., Душеба В.В. Методы организации ортогональных многопроцессорных систем. II // Электронное моделирование. - 2000. - 22, № 1. - С. 59-73.

5. Сигарев А.А., Душеба В.В. Методы построения универсальных ортогональных многопроцессорных систем // Электронное моделирование. - 2000. - 22, № 4. - С. 32-41.

6. Процессорный модуль: А.с. 1674111 СССР, G 06 F 7/544 / В.Ф. Евдокимов, Н.Ю. Пивень, Ю.Ю. Чернышев, П.Н. Владимирский, В.В. Душеба. - № 4646208/24; Заявлено 03.02.89; Опубл. 30.08.91, Бюл. № 32. - 5 с. ил.

7. Устройство для вычисления полиномов: А.с. 1674112 СССР, G 06 F 7/544 / В.Ф. Евдокимов, Н.Ю. Пивень, Ю.Ю. Чернышев, П.Н. Владимирский, В.В. Душеба. - № 4657003/24; Заявлено 28.02.89; Опубл. 30.08.91, Бюл. № 32. - 5 с. ил.

8. Евдокимов В.Ф., Пивень Н.Ю., Чернышев Ю.Ю., Душеба В.В. Организация вычислений на основе обобщенного подхода к решению систем уравнений: Препр. / АН УССР. ИПМЭ; 90-36. - К.: 1990. - 46 с.

9. Пивень Н.Ю., Душеба В.В., Чернышев Ю.Ю. Решение задач аппроксимации функций на специализированном вычислительном устройстве // Ред. ж. Электронное моделирование. - Киев, 1987. - 10с. Деп. в ВИНИТИ 07.08.87г., № 5731-В87.

10. Евдокимов В.Ф., Душеба В.В. Об одном подходе к организации специализированного программного обеспечения функционально ориентированных систем // Труды II Республик. конф. “Функционально ориентированные вычислительные системы” (ФОВС-II). - Харьков. - 1990.

11. Душеба В.В. Организация специализированной памяти функционально ориентированной вычислительной системы // Труды II Республик. конф. “Функционально ориентированные вычислительные системы” (ФОВС-II). - Харьков. - 1990.

12. Чернышев Ю.Ю., Душеба В.В., Владимирский П.Н. Модель обобщенного алгоритма решения систем алгебраических и дифференциальных уравнений // Всесоюз. конф. “Математическое моделирование в энергетике” (ЭПМО-90). - Ч.4. - Киев: ИПМЭ АН УССР. - 1990.

Анотації

Душеба В.В. Організація паралельних процесів у спеціалізованих обчислювальних системах з ортогональним доступом до пам'яті. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 - обчислювальні машини, системи та мережі. - Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, Київ, 2002.

Дисертація присвячена вирішенню задачі організації ефективної взаємодії паралельних обчислювальних процесів у багатопроцесорних обчислювальних системах з ортогональним доступом до пам'яті, що забезпечує скорочення витрат корисного комп'ютерного часу і дозволяє будувати системи, що відображаються різними структурними графами.

У роботі запропоновано методи організації ортогональних багатопроцесорних обчислювальних систем з розшаруванням і перемиканням. Сформульовано принципи міжпроцесорного обміну і його синхронізації, запропоновано новий метод міжпроцесорного обміну, головна відмінність якого полягає у розробленому порядку виконання адресних арифметико-логічних операцій. Такий підхід забезпечує можливість використання стандартних операцій як операції обміну і дозволяє зменшити складність програмних засобів синхронізації та забезпечення безконфліктності обмінних процесів. Проведено експериментальні дослідження на моделюючому стенді системи двох спеціальним чином організованих двопортових буферів пам'яті, використання яких в ортогональних багатопроцесорних системах знімає обмеження на клас задач, що вирішуються і дозволяє будувати системи, які відображаються будь-якими структурними графами.

Ключові слова: багатопроцесорні обчислювальні системи, асинхронний міжпроцесорний обмін, паралельні обчислювальні процеси, ортогональний доступ до пам'яті, узгоджена пара буферів пам'яті, що перемикаються, синхронізація обмінних операцій, когерентний стан пам'яті, узагальнена математична модель.

Dusheba V.V. Organization of parallel processes in the specialized computing systems with orthogonal access to memory. - Manuscript.

The thesis for obtaining candidate of science degree on speciality 05.13.13 - computers, systems and networks. - The Institute of Modelling Problems in Power Engineering by G.E. Puhov of the National Academy of Science of Ukraine, Kiev, 2002.

Dissertation is devoted to the problem of an interaction organization of parallel computing processes in multiprocessor computing systems with orthogonal access to memory, that provides reduction of expenses of useful computer time and allows to build systems displayed by the various structural graphs.

The methods are proposed for the organization of orthogonal multiprocessor computing systems with stratification and switching. The principles of an interprocessor exchange and its synchronization are formulated, the new method of an interprocessor exchange is offered, which main difference consists in the developed order of performance of address arithmetic-logic operations. Such approach provides an opportunity of use of standard operations as operations of an exchange and allows reducing complexity of program procedure of synchronization and providing unconflictness of exchange processes. The system two by the specially organized two-port buffers of memory is experimentally explored on the simulating equipment. Use it removes limitations in orthogonal multiprocessor systems on the class of problems to be solved and allows the construction of systems represented by any structural graphs.

Key words: multiprocessor computing systems, asynchronous interprocessor exchange parallel computing processes, orthogonal access to memory, coordinated pair of switched memory buffers, synchronization of exchange operations, coordinated condition of memory, generalized mathematical model.

Душеба В.В. Организация параллельных процессов в специализированных вычислительных системах с ортогональным доступом к памяти. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - вычислительные машины, системы и сети. - Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины, Киев, 2002.

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

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

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

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

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

Ключевым элементом в разработанной модели обмена является переключаемый буфер памяти, а специальным образом организованные матрицы таких буферов выполняют функции единого пространства памяти вычислительной системы, предназначенного исключительно для информационного обмена. Каждый элемент такой матрицы может поочередно входить в состав ОЗУ двух сопряженных с ним процессоров. Буфер памяти передается программно сопряженному процессору, обладающему программно-аппаратным механизмом такой передачи, но не имеющему механизма захвата буфера. Для процессора имеет значение само подключение (или не подключение) к нему буфера памяти. Поэтому обращение к буферу осуществляется без предварительного программного анализа наличия соответствующей информации.

...