МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
КОНСПЕКТ ЛЕКЦІЙ
з дисципліни “Дослідження та проектування спеціалізованих комп’ютерних систем”
для студентів спеціальності 7.091503 та магістрів спеціальності 8,091503 “Спеціалізовані комп’ютерні системи”
Львів-2004
Конспект лекцій з дисципліни “Дослідження та проектування спеціалізованих комп’ютерних систем” охоплює 5 лекції з питань побудови та проектування складових компонентів комутаторів спеціалізованих комп’ютерних систем та мереж. Для студентів спеціальності 7.091503 та магістрів спеціальності 8,091503 “Спеціалізовані комп’ютерні системи”
Укладач Дунець Б.Р., ст. викладач
Рецензенти Черкаський М.В., д.т.н., проф.
Троценко В.В., к.т.н., доц.
ЗМІСТ
Лекція 1 “Пристроїв комутації пакетів. Класифікація.” 4
Лекція 2 “Буферизація в комутаторах” 11
Лекція 3,4 “ ПКПД матричного типу з вхідною буферизацією, алгоритми планування комутації ” 14
Лекція 5 “Пристрої комутації пакетів з багатоканальною вхідною буферизацією.” 25
Швидкий паралельний метод планування комутації 27
Література 30
Лекція 1 “Пристроїв комутації пакетів. Класифікація.”
Одним із основних елементів сучасних систем передачі інформації, комп’ютерних систем на кристалі та багатопроцесорних комп’ютерних систем є пристрої комутації пакетів даних (ПКПД) (комутатори), які використовуються для об’єднання компонентів системи та обміну інформацією між ними.
Зокрема, в сучасних комунікаційних системах (ATM, BISDN, Ethernet) широко використовуються комутатори пакетів, які забезпечують передачу пакетів даних з вхідних портів на вихідні. Основними елементами таких ПКПД є: пристрій вводу, пристрій виводу, пристрій керування та комутуюче середовище (КМС) (рис.1). Пакети, що поступають в ПКПД послідовно опрацьовуються пристроями вводу, КМС та пристроями виводу. Пристрій керування виконує аналіз пакетів (їх заголовків) та виконує планування комутації. Планування комутації це – визначення послідовності передачі пакетів з вхідних портів у вихідні, яке забезпечує досягнення необхідних характеристик ПКПД. КМС згідно інформації з пристрою керування, виконує фізичне встановлення зв’язку, яке забезпечує передачу пакетів з вхідних портів у вихідні.

Рис.1. Структура пристрою комутації пакетів даних.
Сучасні архітектури комп’ютерних обчислювальних систем та комп’ютерних системах на кристалі групуються навколо ідей паралельної обробки, що в свою чергу потребує паралельного багатоканального доступу до розподілених ресурсів, таких як, наприклад, блоки зовнішньої пам’яті. З метою обміну інформацією та спільного доступу до розподілених ресурсів в таких системах використовуються контролери багатоканального доступу (КБД). КБД забезпечують високоефективний доступ до спільних ресурсів, що досягається комутацію пакетів з вхідних портів запитів у вихідні порти доступу та передачу пакетів даних, що відповідають вхідним запитам у зворотньому напрямку. КБД складається з пристрою вводу/виводу, пристрою керування, пристрою сортування та КМС (рис.2). Пакети, що поступають в комутатор через пристрої вводу/виводу поступають в КМС, яким виконується комутація вхідних пакетів на відповідні пристрої вводу/виводу, які передають запити та очікують даних, що відповідають даним запитам від кінцевих пристроїв. Отримані дані поступають в пристрій сортування та у визначені моменти часу передається у вихідні порти. Пристрій керування виконує аналіз вхідних пакетів запитів та виконує планування комутації вхідних пакетів у вихідні кінцеві пристрої.
Зауважимо, що основними спільними елементами ПКПД та КБД є КМС та пристрій керування, які виконують планування та комутацію пакетів. Тому в подальшому будемо проводити аналіз та синтез тільки ПКПД, розуміючи, що ПКПД є основним складовим елементом КБД.
Пакети даних, що поступають в ПКПД не є сплановані, тому виникає ситуація, при якій декілька пакетів вхідних даних, одночасно мають бути зкомутувані на один вихідний порт. Така ситуація називається вихідним змаганням (конфліктом). Подолання вихідного конфлікту та існуючого в деяких типах комутаторів внутрішнього блокування є основною задачею, що вирішується різними методами побудови ПКПД із застосуванням ефективних алгоритмів планування комутації. Від ефективності вибраного методу побудови комутаторів та алгоритму планування комутації залежать характеристики ПКПД (КБД). Необхідно зазначити, що широкого застосування набули пристрої комутації, що опрацьовують пакети даних фіксованої довжини, що обумовлено перевагами в порівнянні з пристроями комутації пакетів змінної довжини а саме:
- прогнозований час затримки ;
- фективний та простий механізм розміщення буферів та перерозподіл буферів;
- проста система керування, яка функціонує при достатньо малій кількості буферів;
- проста інтеграції з іншими компонентами системи НВІС.

Рис.2. Структура контролера багатоканального доступу.
За останні роки було запропоновано багато структур ПКПД, які поділяють на два класи: ПКПД з часовим розподілом комутації та ПКПД з просторовим розподілом комутації. ПКПД з часовим розподілом комутації, в свою чергу, можна поділити на ПКПД зі спільною пам’яттю та спільним середовищем, а ПКПД з просторовим розподілом – на три підкласи: ПКПД матричного типу, ПКПД бан’янового типу та ПКПД з N2 розділеними зв’язками. Залежно від способу організації ПКПД та КМС необхідним є наявність певного типу буферної пам’яті для забезпечення ефективної його роботи. Буферна пам’ять може бути розміщена на вході – вхідна буферизація, на виході – вихідна буферизація, в КМС – розподілена чи суміщена. При побудові ПКПД можливе використання декількох способів розміщення буферної пам’яті. Необхідно зазначити, що з однієї сторони тип ПКПД однозначно визначає множину типів буферної пам’яті, які є ефективними в поєднанні з даним ПКПД, а з іншої – тип буферної пам’яті задає можливі типи ПКПД (рис.3).

Рис.3. Класифікація пристроїв комутації пакетів.
В ПКПД з часовим розподілом, вхідні пакети комутуються на комунікаційний шлях, який є спільним для вхідного та вихідного каналів (портів). Даний комунікаційний шлях може бути побудований з використанням спільної пам’яті або спільного КМС. Основною проблемою при реалізації ПКПД зі спільною пам’яттю є потреба в високопродуктивній спільній пам’яті, проектування якої наштовхується на труднощі. Так, при швидкості поступлення даних по каналу V біт/сек., пам’ять повинна мати продуктивність 2NV біт/сек. (N – кількість каналів), оскільки вхідний контролер ПКПД послідовно опрацьовує N вхідних пакетів та вибирає N вихідних пакетів протягом періоду поступлення пакету. Обмеження продуктивності пам’яті усувається використанням паралельної організації пам’яті. Розмір пам’яті залежить як від кількості вхідних та вихідних каналів N, так і від інтенсивності поступлення вхідних пакетів та від характеру розподілу вхідних запитів. В загальному випадку пам’ять може бути організована двома шляхами:
Розподілена пам’ять. В даному випадку кожна вихідна черга має певну фіксовану кількість виділених комірок пам’яті. Пакет, призначений для певного вихідного порту втрачається при умові переповнення виділеного для даного вихідного порту блоку пам’яті, хоча інші блоки в цей час можуть бути порожніми. Це є результатом неефективного використання пам’яті при існуючому характері поступлення вхідних даних.
Суміщена пам’ять. Розподіл спільного простору пам’яті між усіма вхідними портами дозволяє ефективно використовувати її у відповідності до характеру вхідного потоку даних. В даному випадку пам’ять буде переповнена при поступлення при вибуховому характері поступлення вхідних даних у всім вхідних портах.
ПКПД зі спільним середовищем використовують в якості КМС шину чи кільцевий буфер. Всі вхідні пакети синхронно комутуються на високопродуктивну паралельну шину, що працює зі швидкістю в N+1 раз більшою ніж частота поступлення запитів. Вихідний інтерфейс складається з фільтра адрес та вихідної пам’яті типу FIFO. Основна проблема, яка виникає при реалізації даного типу ПКПД – це високопродуктивна шина та буферні елементи, швидкодія яких повинна бути рівною (N+1)*V, де V – швидкодія порта. Перевагою ПКПД даного типу є забезпечення максимальної пропускної здатності при мінімальній затримці пакетів.
В комутаторах з просторовим розподілом за допомогою КМС встановлюється декілька комутуючих шляхів між вхідними та вихідними портами, кожен з яких функціонує на частоті поступлення даних. При даному типі комутації, можливою є ситуація, при якій не вдається встановити всі не