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

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

Національний університет "Львівська політехніка"

УДК 004.713, 004.27

Спеціальність 05.13.13 - Обчислювальні машини,

системи та мережі

Автореферат

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

кандидата технічних наук

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

Дунець Богдан Романович

Львів - 2004

Дисертацією є рукопис

Робота виконана в Національному університеті "Львівська політехніка" Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Мельник Анатолій Олексійович, завідувач кафедри електронних обчислювальних машин Національного університету "Львівська політехніка".

Офіційні опоненти:

доктор технічних наук, професор Николайчук Ярослав Миколайович, завідувач кафедри спеціалізованих комп'ютерних систем Тернопільської академії народного господарства;

кандидат технічних наук, старший науковий співробітник Варіченко Леонід Вікторович, директор Державного науково-дослідного підприємства "КОНЕКС" (м. Львів).

Провідна установа: Національний технічний університет України "Київський політехнічний інститут", кафедра обчислювальної техніки, м. Київ.

Захист відбудеться " 15 " лютого 2005 р. о " 16 " год. на засіданні спеціалізованої вченої ради Д 35.052.05 при Національному університеті "Львівська політехніка" за адресою:79013, м. Львів, вул. С. Бандери, 12.

З дисертацією можна ознайомитися у науково-технічній бібліотеці Національного університету "Львівська політехніка" за адресою: 79013, м. Львів, вул. Професорська,1.

Автореферат розісланий "13" січня 2005р.

Вчений секретар спеціалізованої вченої ради, доктор технічних наук, професор Федасюк Д.В.

Анотації

Дунець Б.Р. Пристрої комутації пакетів даних з багатоканальною вхідною буферизацією. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 - обчислювальні машини, системи та мережі. - Національний університет "Львівська політехніка", Львів, 2004.

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

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

Створені VHDL моделі та синтезовані НВІС на ПЛІС ППК, КБД та генератор ядер КБД в порівнянні з відомими рішеннями, мають кращі технічні характеристики.

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

Дунец Б.Р. Устройства коммутации пакетов данных с многоканальной входной буферизацией. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - вычилительные машины, системы и сети. - Национальный университет "Львовская политехника", Львов, 2004.

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

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

Созданные VHDL модели и синтезированные СБИС на ПЛИС УПК, КМД и генератор ядер КМД по сравнению с известными решениями имеют лучшие технические характеристики.

Ключевые слова: коммутация, пакеты данных, алгоритмы планирования коммутации, компьютерные системы, компьютерные сети, системы на кристалле.

Dunets B.R. Data packet switching devices with multichannel input buffering. - Manuscript.

Thesis for the Ph.D. (candidate of science) degree on speciality 05.13.13 - Computing machines, systems and networks.- Lviv Polytechnic National University, Lviv, 2004.

The dissertation deals with development of the new fixed-size packet switches, which operates on line speed with maximum throughput and minimum cell mean delay time.

Because of the unscheduled nature of arrivals to a packet switch, two or more packets may arrive on different inputs destined for the same output. The switch architecture may allow one of these packets to pass through to the output, but the others must be queued for later transmission. In order to improve switch performance due to internal blocking and congestion, queuing is usually employed. Four different queuing approaches of packet switches, including input queuing (IQ), input smoothing, output queuing (OQ), and shared buffering. The conducted investigations show, what an IQ packet switch in combination with scheduling algorithm allows to reach maximum throughput and operates on line speed. But IQ packet switch does not perform minimum cell delay time, which is critical for advanced application. Conducted in the dissertation investigations show - common property of IQ switch is selection at most one cell in one time slot from input buffer. Such property causes not optimal cell mean delay time in IQ switches.

In the dissertation proposed new method, which allows to extracting more than one cell in time slot from input buffer. This method consists of packet switching architecture with multichannel input buffering and new fast parallel scheduling algorithm. Simulation and analytical result shows what the proposed method allows creating switch with the next characteristics: 1. 100% throughput; 2. Cell mean delay time is equal to OQ switch; 3. Switch operates on line speed; 4. Low time scheduling algorithm complexity O(log2N).

On the base of proposed method new packet switch architectures and design methodology have proposed. The proposed switch architectures have divided on two classes: packet switch with reduced (PSR) window size and packet switch with full window size (PSF). Switches of the PSF class perform packet switching with necessary throughput with minimum mean cell delay time. Input queue switches and Multichannel Access Controllers belong to the PSF class of switches. Switches of the PSR class perform switching with maximum throughput with minimum mean cell delay time. Space scheduling division switched and virtual output queue switches belong to the PSR class of switches.

Proposed method and design methodology was used to develop VHDL-model of the single output 64 input port packet switch scheduler. Designed scheduler can be used in fixed size packet switch IP cores development. Implementation in Xilinx and Altera FPGA shows the best characteristics comparing to existing packet switch schedulers. On the base of proposed approach the Multichannel Access Controller VHDL-model was developed. Proposed Multichannel Access Controller provides complete memory subsystem for SOC, it allows to increase a memory bandwidth by multiple RAM block usage. Implementation in Xilinx and Altera FPGA shows the best characteristics comparing to existing memory access controllers. According to the proposed Controller architecture Multichannel Access Controller IP Cores Generator was created. Generator allows generating fully synthesable Register-Transfer-Level Controller VHDL-model by user-defined number of input requests, number of RAM blocks.

Key words: switches, data packets, scheduling algorithms, computer systems, and computer networks, systems on a chip.

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась згідно з планом науково-дослідних робіт кафедри електронних обчислювальних машин Національного університету "Львівська політехніка" протягом 1999 - 2004 рр. Дисертаційна робота безпосередньо пов'язана з держбюджетними темами, де автор був одним із виконавців робіт:

- ДБ.17.ЕС "Розробка нових принципів побудови вимірювально-обчислювальних мереж з елементами самоорганізації для екологічного моніторингу", 2000-2001 р. (номер державної реєстрації 0100U000530).

- ДБ.17.МЕЛЬ "Інтелектуальні реконфігуровані нарощувані вимірювально-обчислювальні мережі екологічного моніторингу: принципи структурної самоорганізації та функціонування", 2002-2003 р. (номер державної реєстрації 0102U001163).

- ДБ/АВАГ "Конфігуровані вимірювально-обчислювальні мережі інтелектуальних автономних агентів для вирішення задач моніторингу навколишнього середовища", 2004 р. (номер державної реєстрації 0104U002284)

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

Для досягнення мети в роботі розв'язані наступні задачі:

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

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

Розробка структури та оцінка характеристик пристрою планування комутації, в якому реалізовано запропонований метод планування комутації.

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

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

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

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

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

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

При цьому отримано такі основні наукові результати:

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

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

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

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

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

Практичне значення одержаних результатів.

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

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

Розроблена VHDL-модель пристрою планування комутації може бути використана при проектуванні НВІС пристроїв комутації пакетів даних.

Розроблена VHDL-модель контролера багатоканального доступу може бути використана при побудові спеціалізованих НВІС та систем на кристалі.

Розроблений генератор ядер контролерів багатоканального доступу дозволяє автоматично генерувати широкий спектр ядер з необхідними характеристиками на основі заданих користувачем параметрів, що дозволяє скоротити час на проектування НВІС контролера.

Впровадження результатів роботи. Теоретичні та практичні результати роботи використані та впроваджені при викладанні дисциплін "Теорія та проектування комп'ютерних систем та мереж", "Проектування НВІС", "Напрямки розвитку спеціалізованих комп'ютерних систем" на кафедрі електронних обчислювальних машин Національного університету "Львівська політехніка", в науково-дослідних роботах по темах, ДБ 17.ЕС "Розробка нових принципів побудови вимірювально-обчислювальних мереж з елементами самоорганізації для екологічного моніторингу", 2000-2001 р., ДБ.17.МЕЛЬ "Інтелектуальні реконфігуровані нарощувані вимірювально-обчислювальні мережі екологічного моніторингу: принципи структурної самоорганізації та функціонування", 2002-2003 р., ДБ/АВАГ "Конфігуровані вимірювально-обчислювальні мережі інтелектуальних автономних агентів для вирішення задач моніторингу навколишнього середовища", 2004 р., ТзОВ "Інтрон" (м. Львів) в рамках створення генератора ядер контролера багатоканального доступу та ТзОВ "Інтех-Л" (м. Львів) в рамках створення маршрутизатора IM100RW. комутація буферизація багатоканальний

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

В друкованій праці [5], опублікованій в співавторстві, автору дисертації належить отримання методики оцінки динамічних та статичних характеристик контролера багатоканального доступу.

Апробація результатів дисертації. Основні положення й результати дисертаційної роботи доповідались й обговорювались на: Четвертій міжнародній конференції "Інформаційні технології друкарства: Алгоритми, сигнали, системи "ДРУКОТЕХН-2002" (Львів, Україна, 7-9 листопада, 2002 р.), науково-технічній конференції "Самсунг. День молодих вчених" (Київ, Україна, 20-21 листопада, 2002 р.), 7-й Міжнародній науково-технічній конференції "Досвід розробки та застосування САПР в мiкроелектронiцi" (Славсько, Україна, 18-22 лютого, 2003 р.), 1-й міжнародній науково-технічній конференції "Сучасні комп'ютерні системи та мережі: розробка та використання" (Львів, Україна, 24-26 вересня, 2003 р.).

Публікації. За результатами виконаних досліджень опубліковано 7 робіт загальним об'ємом 43 сторінки, з них 5 статей в фахових наукових журналах та збірниках, 2 матеріалів доповідей в збірниках міжнародних науково-технічних конференцій.

Структура та обсяг роботи. Дисертаційна робота складається зі вступу, чотирьох розділів, висновку, списку використаних джерел і трьох додатків. Загальний об'єм роботи 184 сторінок. Основний зміст викладений на 127 сторінках. Робота містить 63 рисунки, 11 таблиць. Список використаних джерел з 121 найменувань. Додатки на 62 сторінках.

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

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

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

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

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

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

В роботі доведено, що пропускна здатність ПКПД з багатоканальною вхідною буферизацією прямує до 1 при

.

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

.

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

Пристрій комутації пакетів згідно запропонованого методу складається з вхідного буферу Q, що представляється масивом буферів пакетів Q=[qi,k], i=1,2,…,M, k=1,2,…,W, пристрою планування комутації (ППК) та КМС, де M - кількість входів, N - виходів ПКПД. В ПКПД за кожен часовий проміжок t поступає тільки один пакет в кожен з вхідних портів.



Рис.1. Структура ПКПД з багатоканальною вхідною буферизацією

Означення 1. Матриця вхідних ідентифікаторів H(t)=[hi] - це матриця-стовпець, елементами якої є ідентифікатори hi(t), які в кожному часовому проміжку t разом з вхідними пакетами поступають в ПКПД та містять для кожного входу i=1,2,…M номер вихідного порта j=1,2,…,N, на який даний пакет має бути зкомутований. Якщо h i(t) =0, то пакет - відсутній.

При поступленні в момент часу t множини вхідних пакетів A(t), дані пакетів зберігаються в масиві Q(t), а відповідні ідентифікатори H(t) поступають в ППК. Для моменту часу t (часового проміжку) ППК на основі отриманих вхідних ідентифікаторів визначає вектор комутації S(t)=[sj], j=1,2,…,N, який містить слово комутації sj для кожного j-го вихідного порта. Слово комутації sj містить пакет масиву Q, який комутується за допомогою комутуючої мережі на вихід j.

Означення 2. Матриця ідентифікаторів V(t)=[vi,k] - це масив, елементами якого є ідентифікатори vi,k, де vi,k =hi(t-k-1), i=1,2,…,M, k=1,2,…,W. В матриці ідентифікаторів містяться ідентифікатори вхідних пакетів, що поступили в ППК та підлягають плануванню.

Означення 3. Матриця вибору G(t)=[gj,k] - це масив, елементами якого є числові значення номеру стовпця матриці ідентифікаторів, де j=1,...,N, k=1,..,W. Матриця вибору призначена для вибору та зберігання для кожного виходу та часового проміжку тільки одного ідентифікатора.

З метою подальшого спрощення опису методу планування комутацією введено функцію вертикального вибору V_SEL(V(t),j,k) та функцію горизонтального вибору H_SEL(G(t),j), які виконують пошук та вибір елементів матриць V(t) та G(t) згідно певних критеріїв.

Функція вертикального вибору V_SEL(V(t),j,k) виконує пошук елемента, значення якого рівне j серед елементів k-того стовпця матриці V(t). Функція повертає номер рядка елемента, або 0 у випадку відсутності в рядку елемента, значення якого рівне j. У випадку наявності декількох елементів в k-му стовпці матриці V(t), функція повертає найбільший номер рядка.

Функція горизонтального вибору H_SEL(G(t), j) виконує пошук серед елементів j-того рядка матриці G(t) значення ненульового елемента. Якщо такий елемент gj,k знайдено, то функція повертає пару чисел {i,k}, де i=gj,k та k - номер стовпця знайденого елемента. У випадку наявності декількох ненульових елементів в j-му рядку матриці G(t), функцією вибирається елемент з найбільший номером стовпця. У випадку відсутності в j-му рядку ненульових елементів функція повертає {0,0}.

Згідно швидкого паралельного методу планування комутації в кожному часовому проміжку t виконується планування комутації в наступній послідовності дій:

Крок 1. Вертикальний пошук.

Обчислення за допомогою функції вертикального вибору значень матриці вибору gj,k=V_SEL(V(t), j,k), для кожної пари j та k, де j=1,2,…,N та k=1,2,…,W.

Крок 2. Горизонтальний пошук.

Обчислення за допомогою функції горизонтального вибору значень вектору комутації sj=H_SEL(G(t), j), для кожного j=1,2,…,N.

Крок 3. Підтвердження та комутація.

Для кожного вихідного порта j=1,2,…,N виконується комутація, згідно вектору комутації та встановлення в 0 значення відповідних комірок матриці комутації, що відповідають зкомутованим пакетам на даному кроці:

Dj(t):=vi,k, vi,k:=0, де {i,k}=si. D(t) - множина вихідних пакетів.

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

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

В роботі запропонована базова структура пристрою планування комутації, яка дозволяє реалізувати швидкий паралельний метод планування комутації апаратно. Пристрій планування комутації (рис.3) складається з W блоків вертикального пошуку (БВП), блоку горизонтального пошуку (БГП), блоку обчислення кількості втрачених пакетів (БОВП).

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

Затрати обладнання на реалізацію ППК залежать від розміру вікна обслуговування W та кількістю вхідних M і вихідних портів N. Ці затрати АППК визначаються за формулою:

AППК= W*(M*AРГ + N*AI]log2M[)+ 2*N*M* AI2*]log2M[+

+ N(WAРГ+(W-1)AВІДН+(W-1)*AI2+AМП,) +AБОВП, (1)

де АРГ - затрати обладнання на реалізацію регістра розрядністю ]log2N[, АI]log2M[ - затрати на реалізацію логічного елемента "І" розрядністю ]log2M[, AI2 - затрати на реалізацію елемента "І", AВІДН - затрати на реалізацію віднімача, АМП - затрати на реалізацію мультиплексора на W входів розрядністю ]log2M[, АБОВП - затрати на реалізацію лічильника.

Рис.2. Графіки залежності середнього часу затримки від інтенсивності поступлення вхідних даних при рівномірному розподілі вхідних запитів на вихідні порти



Рис.3. Структура пристрою планування комутації

У третьому розділі розроблено нову базову структуру пристрою комутації пакетів даних з багатоканальною вхідною буферизацією. Такий пристрій (рис.4) складається з M багатоканальних вхідних буферів (ВхБ), комутуючого середовища (КМС), пристрою планування комутації (ППК). Вхідні пакети поступають у відповідні ВхБ, а ідентифікатори пакетів поступають в ППК та ВхБ. ППК згідно алгоритму планування виконує пошук вектора комутації S(t)=s1,…,sN. Кожен елемент вектора комутації містить номер ВхБ, який повинен передати на свою вихідну шину пакет. Так, елемент вектора комутації sj містить номер ВхБ, який повинен передати пакет на свій вихід з номером j. Оскільки, вектор комутації містить N елементів, то кількість переданих пакетів одним ВхБ може досягати N, кількість переданих пакетів усіма ВхБ не перевищує N. Вибрані пакети за допомогою КМС передаються з ВхБ у вихідні порти.

Запропонована базова структура ПКПД з багатоканальною буферизацією є основою розроблених базових структур ПКПД двох класів: ПКПД із повним вікном обслуговування (ПКПД з ПВ) та ПКПД зі скороченим вікном обслуговування (ПКПД з СВ). Під скороченим вікном обслуговування розуміється зменшений розмір вікна обслуговування ППК ПКПД за умови, що пропускна здатність його рівна пропускній здатності ПКПД, розмір вікна ППК якого є більшим. Характеристики ПКПД з ПВ залежать від розміру вікна обслуговування і визначаються характеристикам ППК для заданого вікна обслуговування W. В пристроях комутації такого класу використовується розмір вікна обслуговування, достатній для забезпечення необхідної пропускної здатності. ПКПД з ПВ призначені для використання в системах, де досягнення максимуму пропускної здатності ПКПД не є критичним. Запропоновано базові структури ПКПД з ПВ а саме: ПКПД з вхідною буферизацією (ПКПД з ВхБ) (рис.4), контролерів багатоканального доступу (КБД). В роботі проведено оцінку технічних характеристик ПКПД з ВхБ, які показали, що ПКПД даного типу забезпечують комутацію пакетів з необхідною пропускною здатністю та з мінімальним середнім часом затримки комутації пакетів, при цьому ПКПД з ВхБ забезпечують більшу пропускну здатність при заданому розмірі вікна обслуговування в порівнянні з відомими аналогами.

В роботі розроблено базову структуру та проведено оцінку технічних характеристик КБД, які забезпечують багатоканальний доступ з N вхідних каналів запитів Ai (i=1,2,…,N) до M розподілених ресурсів, таких як блоки зовнішньої пам'яті Rj (j=1,2,..,M) (рис.5). КБД проводить обслуговування запитів, що полягає в записі та читанні інформації в/з блоків пам'яті та видачу прочитаних даних (для запитів типу "читання") на відповідних вихідних лініях даних Di (i=1,2,…,N). Планування доступу до блоків зовнішньої пам'яті виконується блоками планування доступу (БПД), які функціонують згідно запропонованого алгоритму ШПАК. Проведені в роботі дослідження показали, що запропоновані КБД забезпечують більшу пропускну здатність у порівнянні з відомими аналогами.



Рис.4. Базова структура ПКПД з багатоканальною вхідною буферизацією

Рис.5. Базова структура контролера багатоканального доступу

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

В роботі запропоновано ряд нових рішень побудови ПКПД, які забезпечують досягнення більшої пропускної здатності при розмірах вікна обслуговування менших від теоретично необхідного за рахунок зменшення переповнення. При цьому, максимальна пропускна здатність ПКПД досягається при значеннях вікна обслуговування . Дані рішення лягли в основу базових структур ПКПД з СВ, а саме: ПКПД з часовим розподілом планування комутації (ПКПД з ЧРП), ПКПД з просторовим розподілом планування комутації (ПКПД з ПРП), ПКПД з віртуальною вихідною буферизацією (ПКПД з ВВихБ). Структура ПКПД з СВ загалом аналогічна структурі ПКПД з ВхБ, за винятком ППК. Зокрема, досягнення необхідної пропускної здатності в ПКПД з ЧРП досягається завдяки використанню часового розподілу планування комутації. При часовому розподілі планування комутації ППК працює на швидкості в K разів більшої швидкості поступлення вхідних пакетів, тому даний пристрій в одному часовому проміжку може виконати планування в K раз більше пакетів, ніж ПКПД з ВхБ, де K - коефіцієнт прискорення. Узгодження швидкостей поступлення вхідних запитів та їх планування досягається використанням вихідної буферизації ППК. Досягнення необхідної пропускної здатності в ПКПД з ПРП досягається при заданих розмірах вікна обслуговування W завдяки використанню C паралельних ППК, кожен з яких працює на швидкості поступлення вхідних запитів.

В роботі запропоновано базову структуру ПКПД з ВвихБ, особливістю якої є наявність спеціалізованого пристрою планування комутації, що дозволяє ефективно усувати переповнення. ППК ПКПД з ВВихБ складається (рис.6) з віртуального вихідного буферу (ВВихБ) та N блоків планування комутації (БПК 1 - БПК N), кожен з яких виконує планування комутації пакетів для одного виходу ПКПД. При цьому, ідентифікатори вхідних пакетів опрацьовуються та буферизуються блоком ВВихБ, який виконує поділ масиву ідентифікаторів вхідних пакетів H(t) на N підмасивів ідентифікаторів вхідних запитів . В результаті кожен з підмасивів ідентифікаторів вхідних запитів містить тільки ідентифікатори, які відносяться до одного виходу. БПК 1 - БПК N є незалежними блоками з ідентичною внутрішньою структурою. Кожен з БПК виконує планування комутації для одного виходу згідно алгоритму ШПАК. Апаратна складність ППК ПКПД з ВВихБ визначається за такою формулою:

АППК=АВВихБ+N*АБПК, (2)

де АБПК - затрати на реалізацію ППК з N=1, визначені згідно формули (1); АВВихБ - затрати на реалізацію ВВихБ ППК, які визначаються за такою формулою:

AВВихБ=N*[4*M*AI2+3*AI2+1.2*M* C*AРГ +M*AМП 2х 1], (3)

де AI2 -затрати обладнання на реалізацію елемента І, AРГ - затрати обладнання на реалізацію однорозрядного регістра, AМП 2х 1 - затрати обладнання на реалізацію однорозрядного мультиплексора.



Рис.6. Базова структура пристрою планування комутації ПКПД з віртуальною вихідною буферизацією

Результати проведених в роботі досліджень показали, що ПКПД з СВ забезпечують комутацію пакетів з мінімальним середнім часом затримки з максимальною пропускною здатністю.

У четвертому розділі На основі запропонованих структур у другому та третьому розділах, було виконано проектування ядра пристрою планування комутацією для M=64, N=1. Структуру ядра пристрою описано мовою VHDL та синтезовано на ПЛІС типу Xilinx та Altera (табл.1). В порівнянні з відомими розроблене ядро має більшу продуктивність планування, дозволяє досягти максимальної пропускної здатності та мінімального середнього часу затримки комутації при побудові НВІС пристроїв комутації пакетів даних з багатоканальною вхідною буферизацією.

Таблиця 1. Результати синтезу ядра ППК на ПЛІС

Фірма вироб-ник	Тип ПЛІС	Затрати обладнання в базових елементах ПЛІС	Тактова частота, МГц	Затрати обладнання, вентилів	Продуктивність планування, запитів/сек.
Xilinx	Virtex II	740 Slices	78	12 тис	78 млн.
Altera	Apex	2632 LE	56	21 тис	56 млн.

На основі запропонованої у третьому розділі базової структури, було виконано проектування ядра контролера багатоканального доступу, що забезпечує обслуговування звертань з 5 ліній вхідних запитів до 3 блоків зовнішньої пам'яті. Структуру ядра контролера описано мовою VHDL та синтезовано на ПЛІС типу Xilinx та Altera (табл.2). В порівнянні з відомими вона забезпечує збільшення продуктивності роботи з зовнішньою пам'яттю не менше, ніж на 20%. Запропонований пристрій може бути використаний при побудові НВІС спеціалізованих комп'ютерних систем та комп'ютерних систем на кристалі.

Таблиця 2. Результати синтезу ядра КБД на ПЛІС

Фірма виробник	Тип ПЛІС	Затрати обладнання в базових елементах ПЛІС	Тактова частота, МГц
Xilinx	Virtex II	1204 Slices	98.3
Altera	Apex20KE	3078 LE	81.42

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

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

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

Основні результати роботи та висновки

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

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

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

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

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

На основі запропонованих структур, було виконано проектування пристрою планування комутації для одного виходу при кількості вхідних ліній запитів рівній 64. Розроблений пристрій мовою VHDL та синтезований на ПЛІС типу Xilinx та Altera в порівнянні з відомими має більшу швидкодію, та може бути використаний при побудові НВІС пристроїв комутації пакетів даних.

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

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

Список праць за темою дисертації

Дунець Б.Р. Швидкий паралельний метод планування комутацією // Вісник НУ "Львівська політехніка" "Комп'ютерні системи та мережі".- 2003. - №492.- С.59-68.

Дунець Б.Р. Архітектура пристрою планування комутацією // Вісник Тернопільського державного технічного університету.- 2003. - Том. 8. - №4.- С.85-91.

Дунець Б.Р. Базові архітектури пристроїв комутації пакетів з багатоканальною вхідною буферизацією // Комп'ютерні технології друкарства.- 2004.- № 11.- C.43-49.

Дунець Б.Р. Архітектура контролера доступу до багатоблокової пам'яті // "Комп'ютерні технології друкарства". -2002. -№ 8. -С.33-39.

Дунець Б.Р., Мельник А.О. Дослідження характеристик контролера доступу до багатоблокової пам'яті // Вісник НУ "Львівська політехніка" "Комп'ютерні системи та мережі".- 2002. -№463. -С.46-51.

Bohdan Dunets Fast Parallel Scheduling Algorithm for ATM Switches //Proc. of the I-іh International Conf. Advanced Computer Systems and Networks: Design and Application. ACSN'2003. - Lviv:Publishing House of Lviv Polytechnic National University. -2003. -P.69-72.

Bohdan Dunets Multiblock RAM Access Controller IP Cores Generator //Proc. of the VII-th International Conf. The Experience of Designing and Aplication of CAD Systems in Microelectronics. CADSM'2003. - Lviv:Publishing House of Lviv Polytechnic National University. -2003. -P.214-215.

Размещено на Allbest.ru

...