Автореферат

Публікаціі

Результати пошука

Дослідження способів розпаралелювання у процесі трансляції

Виконав Нєботов Євген Миколайович

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

Звіт

Вступ

В 70-і роки логічне програмування й бази даних розвивалися одночасно. Пролог - сама популярна мова ПРОграммирования в ЛОГике — з'явився як результат спрощення більше загальних методів доказу теорем для досягнення можливості ефективного програмування. Аналогічно реляционнаа модель даних виникла в результаті спрощення складних ієрархічної й мережної моделей для забезпечення можливості непроцедурного маніпулювання
множинними даними. Протягом 70-х і на початку 80-х років Пролог і реляционнаі бази даних одержали широке поширення не тільки в академічному або науковому середовищі, але й у діловому світі.
Інтенсивні дослідження взаємозв'язку логічного програмування й реляционнаих баз даних проводилися з кінця 70-х років головним чином з теоретичної точки зору. Успіху інтеграції сприяло ту обставину, що Пролог був обраний як парадигма мови програмування в японському проекті IВМ 5-го покоління. Метою цього проекту є розробка «ЕОМ наступного покоління», орієнтованих на застосування в області штучного інтелекту й, отже, здатних виконувати винятково велика кількість логічних висновків в одиницю часу. Але досягти більшої швидкодії можливо лише двома методами: екстенсивним (кращі архітектури, процесори, більша тактова частота) або інтенсивним (оптимізація, розвантаження коду, розпаралелювання). Постійно обновляти й купувати нове дороге обладнання менш рентабельно, чим придбати програмне забезпечення, що працює ефективніше й швидше на будь-якому наявному встаткуванні. Розпаралелювання в процесі трансляції дає перевага в роботі програми, у швидкодії виконуваного коду.

Мотівация

Актуальність роботи

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

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

Дослідженню й рішенню даних питань і присвячена робота.

Мета й задачи дослідження

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

Методи дослідження

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

Научна новизна

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

Практична цінність

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

Звіт роботи

Пролог дуже добре підходить для опису взаємин між об'єктами. Тому Пролог називають реляционнаою мовою. Причому «реляційність» Прологу значно могутніша й розвинена, чим «реляційність» язиків, використовуваних для обробки баз даних. Часто Пролог використається для створення систем керування базами даних, де застосовуються дуже складні запити, які досить легко записати на Пролозі.
У Пролозі дуже компактно, у порівнянні з імперативними мовами, описуються багато алгоритмів. По статистиці, рядок вихідного тексту програми мовою Пролог відповідає чотирнадцяти рядкам вихідного тексту програми імперативною мовою, що вирішує те ж завдання. Пролог-програму, як правило, дуже легко писати, розуміти й налагоджувати. Це приводить до того, що час розробки додатка мовою Пролог у багатьох випадках на порядок швидше, ніж на імперативних мовах. У Пролозі легко описувати й обробляти складні структури даних. Перевіримо ці твердження на власному досвіді при вивченні даного курсу.
Прологу властив ряд механізмів, якими не володіють традиційні мови програмування: зіставлення зі зразком, висновок з пошуком і поверненням. Ще одна істотна відмінність полягає в тім, що для зберігання даних у Пролозі використаються списки, а не масиви. У язиці відсутні оператори присвоювання й безумовного переходу, покажчики. Природним і найчастіше єдиним методом програмування є рекурсія. Тому часто виявляється, що люди, що мають досвід роботи на процедурних мовах, медленней освоюють декларативні мови, чим ті, хто ніколи раніше програмуванням не займався, тому що Пролог вимагає іншого стилю мислення, відмови від стереотипів імперативного програмування.
Як мова програмування Пролог дуже добре підходить для початкового навчання програмуванню, тому що він орієнтованим на людське мислення на відміну від імперативних мов, орієнтованимих на комп'ютер. Тими, хто тільки починає вивчати програмування, Пролог легко освоюється. Практично повна відсутність синтаксичних конструкцій, таких як розгалуження, цикли й т.д. також впливає на швидкість освоєння язика. Крім того, програмування на Пролозі, як мені здається, упорядковує мислення й дозволяє людині, що вивчає цю мову програмування, краще розібратися у своїй розумовій діяльності. Дуже часто для того, щоб запрограмувати рішення завдання, програмістові (або експертові в деякій предметній області) спочатку потрібно зрозуміти, як він сам вирішує це завдання, провести якусь формалізацію, перевести свої знання з неявних у явні.
Розглянемо, у яких областях щонайкраще себе показав Пролог:
-швидка розробка прототипів прикладних програм;
-автоматичний переклад з одного язика на іншій;
-створення природно-язикових інтерфейсів для існуючих систем;
-символьні обчислення для рішення рівнянь, диференціювання й інтегрування;
-проектування динамічних реляционнаих баз даних;
-експертні системи й оболонки експертних систем;
-автоматизоване керування виробничими процесами;
-автоматичний доказ теорем;
-напівавтоматичне складання розкладів;
-системи автоматизованого проектування;
-базоване на знаннях програмне забезпечення;
-організація сервера даних або, точніше, сервера знань, до якого може звертатися клієнтський додаток, написане на якій-небудь мові програмування.
Області, для яких Пролог не призначений: великий обсяг арифметичних обчислень (обробка аудіо, відео й т.д.); написання драйверів.

На сьогодні існує досить багато реалізацій Прологу. Найбільш відомі з них наступні: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, Мпролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic Knowledge Workbench, Strawberry Prolog, SWI Prolog, UNSW Prolog і т.д.
У нашій країні були розроблені такі версії Прологу як Пролог-Д (Сергій Григор'єв), Акторный Пролог (Олексій Морозов), а також Фленг (А. Манцивода, В'ячеслав Петухин).
Таблиця реалізацій Прологу

Реалізації Прологу

Архітектури Обчислювальних систем з паралельною організацією обчислень

Класифікація Флинна

Очевидно, самої ранньої й найбільш відомої є класифікація архитектур обчислювальних систем, запропонована в 1966 році М.Флинном. Класифікація базується на понятті потоку, під яким розуміється послідовність елементів, команд або даних, оброблювана процесором. На основі числа потоків команд і потоків даних Флинн виділяє чотири класи архітектур: SISD,MISD,SIMD,MIMD.

Малюнок 2.1 – SISD
SISD (single instruction stream / single data stream) - одиночний потік команд й одиночний потік даних. До цього класу ставляться, насамперед, класичні послідовні машини, або інакше, машини фон-неймановського типу, наприклад, PDP-11 або VAX 11/780. У таких машинах є тільки один потік команд, всі команди обробляються послідовно один за одним і кожною командою ініціює одну операцію з одним потоком даних. Не має значення той факт, що для збільшення швидкості обробки команд і швидкості виконання арифметичних операцій може застосовуватися конвеєрна обробка - як машина CDC 6600 зі скалярними функціональними пристроями, так й CDC 7600 з конвеєрними попадають у цей клас.

SIMD (single instruction stream / multiple data stream) - одиночний потік команд і множинний потік даних. В архитектурах подібного роду зберігається один потік команд, що включає, на відміну від попереднього класу, векторні команди. Це дозволяє виконувати одну арифметичну операцію відразу над багатьма даними - елементами вектора. Спосіб виконання векторних операцій не обмовляється, тому обробка елементів вектора може виробляється або процесорною матрицею, як в ILLIAC IV, або за допомогою конвеєра, як, наприклад, у машині CRAY-1.

MISD (multiple instruction stream / single data stream) - множинний потік команд й одиночний потік даних. Визначення має на увазі наявність в архітектурі багатьох процесорів, що обробляють той самий потік даних. Однак ні Флинн, ні інші фахівці в області архітектури комп'ютерів дотепер не змогли представити переконливий приклад реально існуючої обчислювальної системи, побудованої на даному принципі. Ряд дослідників відносять конвеєрні машини до даного класу, однак це не знайшло остаточного визнання в науковому співтоваристві. Будемо вважати, що поки даний клас порожній.

Малюнок 4 – MIMD
MIMD (multiple instruction stream / multiple data stream) - множинний потік команд і множинний потік даних. Цей клас припускає, що в обчислювальній системі є кілька пристроїв обробки команд, об'єднаних у єдиний комплекс і працюючих кожне зі своїм потоком команд і даних.
Отже, що ж собою представляє кожен клас? В SISD, як уже говорилося, входять однопроцесорні послідовні комп'ютери типу VAX 11/780. Однак, багатьма критиками помічено, що в цей клас можна включити й вєкторно-конвєєрні машини, якщо розглядати вектор як одне неподільне дане для відповідної команди. У такому випадку в цей клас потраплять і такі системи, як CRAY-1, CYBER 205, машини сімейства FACOM VP і багато хто інших.
Безперечними представниками класу SIMD уважаються матриці процесорів: ILLIAC IV, ICL DAP, Goodyear Aerospace MPP, Connection Machine 1 і т.п. У таких системах єдиний керуючий пристрій контролює безліч процесорних елементів. Кожен процесорний елемент одержує від пристрою керування в кожен фіксований момент часу однакову команду й виконує її над своїми локальними даними. Для класичних процесорних матриць ніяких питань не виникає, однак у цей же клас можна включити й вєкторно-конвєєрні машини, наприклад, CRAY-1. У цьому випадку кожен елемент вектора треба розглядати як окремий елемент потоку даних.
Клас MIMD надзвичайно широкий, оскільки містить у собі всілякі мультипроцесорні системи: Cm*, C.mmp, CRAY Y-MP, Denelcor HEP,BBN Butterfly, Intel Paragon, CRAY T3D і багато хто інших. Цікаво те, що якщо конвєєрну обробку розглядати як виконання безлічі команд (операцій щаблів конвеєра) не над одиночним векторним потоком даних, а над множинним скалярним потоком, те всі розглянуті вище вєкторно-конвєєрні комп'ютери можна розташувати й у даному класі.
Запропонована схема класифікації аж до теперішнього часу є самою застосовуваною при початковій характеристиці того або іншого комп'ютера. Якщо говориться, що комп'ютер належить класу SIMD або MIMD, то відразу стає зрозумілим базовий принцип його роботи, і в деяких випадках цього буває досить. Однак видні і явні недоліки. Зокрема, деякі заслуживаючі уваги архітектури, наприклад dataflow і вєкторно--конвєєрні машини, чітко не вписуються в дану класифікацію. Інший недолік - це надмірне заповнювання класу MIMD. Необхідний засіб, більше виборчий систематизуючого архітектури, які по Флинну попадають в один клас, але зовсім різні по числу процесорів, природі й топології зв'язку між ними, по способі організації пам'яті й, звичайно ж, за технологією програмування.
Наявність порожнього класу (MISD) не варто вважати недоліком схеми. Такі класи, на думку деяких дослідників в області класифікації архітектур , можуть стати надзвичайно корисними для розробки принципово нових концепцій у теорії й практиці побудови обчислювальних систем.

Класифікація Хокни

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

Класифікація MIMD систем
Основна ідея класифікації полягає в наступному. Множинний потік команд може бути оброблений двома способами: або одним конвєєрним пристроєм обробки, що працює в режимі поділу часу для окремих потоків, або кожен потік обробляється своїм власним пристроєм. Перша можливість використається в MIMD комп'ютерах, які автор називає конвєєрними (наприклад, процесорні модулі в Denelcor HEP). Архітектури, що використають другу можливість, у свою чергу знову діляться на два класи:
-MIMD комп'ютери, у яких можлива прямий зв'язок кожного процесора з кожним, реалізована за допомогою перемикача;
-MIMD комп'ютери, у яких прямий зв'язок кожного процесора можлива тільки з найближчими сусідами по мережі, а взаємодія вилучених процесорів підтримується спеціальною системою маршрутизації через процесори-посередники.
Далі, серед MIMD машин з перемикачем Хокни виділяє ті, у яких вся пам'ять розподілена серед процесорів як їхня локальна пам'ять (наприклад, PASM, PRINGLE). У цьому випадку спілкування самих процесорів реалізується за допомогою дуже складного перемикача, що становить значну частину комп'ютера. Такі машини звуться MIMD машин з розподіленою пам'яттю. Якщо пам'ять це поділюваний ресурс, доступний всім процесорам через перемикач, то такі MIMD є системами із загальною пам'яттю (CRAY X-MP, BBN Butterfly). Відповідно до типу перемикачів можна проводити класифікацію й далі: простий перемикач, многокаскадный перемикач, загальна шина.
Багато сучасних обчислювальних систем мають як загальну поділювану пам'ять, так і розподілену локальну. Такі системи автор розглядає як гібридні MIMD c перемикачем.
При розгляді MIMD машин з мережною структурою вважається, що всі вони мають розподілену пам'ять, а подальша класифікація проводиться відповідно до топології мережі: зіркоподібна мережа (lCAP), регулярні решітки різної розмірності (Intel Paragon, CRAY T3D), гіперкуби (NCube, Intel iPCS), мережі з ієрархічною структурою, такий, як дерева, піраміди, кластери (Cm* , CEDAR) і, нарешті, мережі, що змінюють свою конфігурацію.
Помітимо, що якщо архітектура комп'ютера спроектований з використанням декількох мереж з різною топологією, те, як видно, за аналогією з гібридними MIMD з перемикачами, їх варто назвати гібридними мережними MIMD, а ідеї, що використають, різних класів - просто гібридними MIMD. Типовим представником останньої групи, зокрема, є комп'ютер Connection Machine 2, що має на зовнішньому рівні топологію гіперкуба, кожен вузол якого є кластером процесорів з повним зв'язком.

Виводи

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

Список використаноі літератури*