Підвищення ефективності багатоядерних мережних процесорів

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

Державний вищий навчальний заклад

«Донецький національний технічний університет»

Автореферат

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

05.13.05 - комп'ютерні системи та компоненти

Підвищення ефективності багатоядерних мережних процесорів

Грищенко Віктор Ігорович

Донецьк - 2011

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

Робота виконана в Державному вищому навчальному закладі «Донецький національний технічний університет» Міністерства освіти і науки, молоді та спорту України

Науковий керівник: кандидат технічних наук, доцент Ладиженський Юрій Валентинович, ДВНЗ «Донецький національний технічний університет» Міністерства освіти і науки, молоді та спорту України, доцент кафедри «Прикладна математика та інформатика»

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

доктор технічних наук, професор Скобцов Юрій Олександрович, ДВНЗ «Донецький національний технічний університет» Міністерства освіти і науки, молоді та спорту України, завідувач кафедри «Автоматизовані системи управління»;

доктор технічних наук, старший науковий співробітник Алішов Надір Ісмаіл-огли, Інститут кібернетики ім. В.М. Глушкова НАН України, м. Київ, провідний науковий співробітник

Вчений секретар спеціалізованої вченої ради Д11.052.03 Г.В. Мокрий

Анотація

мережний процесор програма

Грищенко В.І. Підвищення ефективності багатоядерних мережних процесорів. -- Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 -- Комп'ютерні системи та компоненти. -- ДВНЗ «Донецький національний технічний університет», Донецьк, 2011.

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

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

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

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

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

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

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

Аннотация

Грищенко В.И. Повышение эффективности многоядерных сетевых процессоров. -- Рукопись.

Диссертация на соискание ученой степени кандидата наук по специальности 05.13.05 -- Компьютерные системы и компоненты. -- ГВУЗ «Донецкий национальный технический университет», Донецк, 2011.

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

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

Проведен анализ особенностей приложений обработки данных, выполняемых на сетевых процессорах. Показано, что использование конвейерной обработки позволяет значительно повысить производительность СП и не требует наличия блока предсказания переходов.

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

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

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

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

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

Проведено исследование работы сетевого процессора с распределенной памятью. Показано, что выделение отдельного блока памяти для кода каждого этапа конвейера на 23% увеличивает производительность системы и уменьшает время обработки пакета в 4 раза по сравнению со структурой с общей памятью.

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

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

Abstract

Grischenko V.I. Increasing efficiency of multi-core network processors. --Manuscript.

The thesis is presented for the obtaining of scientific degree of a candidate of technical science according to the specialization 05.13.05 - Computing systems and components. - SHEE “Donetsk National Technical University”, Donetsk, 2011.

The thesis is devoted to developing multi-core network processors analytical models, developing of integrated modeling techniques and using of the developed technique to study the effectiveness of network processors with different structures.

The network processors analytical models are developed. Performance investigation structures with shared memory, distributed memory and storing network application in the instruction cache are supported by these models.

The methodology and modeling system that improved an integrated approach to network processor modeling are developed. This methodology allows to extend the set of network processors architectures and set of benchmark applications. The simulation system error filtering mechanism is proposed.

The network processor structure parameters, providing the most efficient implementation of dynamic routing algorithm AntNet, is proposed.

A study of network processors with shared memory, distributed memory, and storing networking applications in the instruction cache has done. It is shown that performance of the structure with a shared memory is limited by the external memory. The effective using areas for structures with distributed memory and dedicated instruction cache are determined.

Keywords: computer network, router, network processor, network queuing, integrated simulation technique.

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

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

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

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

Виявлення недоліків апаратних реалізацій маршрутизаторів призвело до початку пошуку рішень, здатних об'єднати в собі гнучкість програмного й високу продуктивність апаратного підходів. Рішенням стало використання програмованих пристроїв зі спеціалізованим набором інструкцій (Application Specific Instruction Processor, ASIP). У процесорах цього типу, мережних процесорах (МП), апаратно реалізуються основні функції мережної обробки даних (підрахунок контрольних сум, розбір заголовків), при цьому надаються широкі можливості для програмування, порівнянні з можливостями процесорів загального призначення.

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

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

Проблемам моделювання обчислювальних пристроїв і мереж присвячена велика кількість досліджень і публікацій. Зокрема можна виділити роботи Палагіна А.В., Глушкова В.М., Королюка В.С., Малиновського Б.М., Фельдмана Л.П., Алішова Н.І., Жукова І.А., Дедіщева В.А., Білецького В.М., Погорілого С.Д., Безрук В.М., Зайцева Д. А. За кордоном слід відзначити роботи Вишневського В.М., Кагана Б.М., Іваницького В.А., Клейнрока Л., Кучерявого О.О., Lothar Thiele, Tilman Wolf, Douglas Comer.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Основні дослідження по темі дисертації проводилися на кафедрі прикладної математики та інформатики ДВНЗ «Донецький національний технічний університет» Д-1-05 «Розвиток теорії мережних інформаційних технологій розподіленого моделювання і синтезу цифрових систем на програмованих пристроях» (номер держреєстрації 0105U002288), Д-1-08 «Розвиток теорії синтезу і розподіленого моделювання високопродуктивних проблемно-орієнтованих обчислювальних систем з програмованими НВІС» (номер держреєстрації 0108U001959), в яких здобувач приймав участь як виконавець.

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

Аналіз структур і методів моделювання сучасних мережних процесорів.

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

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

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

Оцінка впливу параметрів кешу на продуктивність мережного процесора.

Оцінка впливу структури МП на його ефективність.

Об'єкт дослідження. Процес обробки потоків даних в мережних процесорах.

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

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

Наукова новизна отриманих результатів:

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

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

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

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

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

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

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

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

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

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

Результати дисертаційного дослідження використано у науково-виробничому підприємстві ТОВ “АМІ” (м. Донецьк) при розробці підсистеми маршрутизації комп'ютерних мереж; в науково-дослідних роботах Донецького національного технічного університету № Д-1-05 «Розвиток теорії мережних інформаційних технологій розподіленого моделювання та синтезу цифрових систем на програмуємих пристроях» (номер держ. реєстрації 0105U002288) та № Д-1-08 «Розвиток теорії синтезу і розподіленого моделювання високопродуктивних проблемно-орієнтованих обчислювальних систем з програмованими НВІС» (номер держ. реєстрації 0108U001959); у навчальному процесі при читанні лекцій з курсів “Комп'ютерні мережі”, “Теорія та організація розподіленої обробки даних в комп'ютерних мережах” та “Архітектура комп'ютера”.

Апробація роботи. Основні положення та результати роботи доповідалися, обговорювалися і отримали позитивну оцінку на міжнародних науково-технічних конференціях: «Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій» (м. Запоріжжя, 13-15 квітня 2006 року), «Інтернет - Освіта - Наука - 2006» (м. Віниця, 10-14 жовтня 2006 року), «Гарантоспроможні (надійні та безпечні) системи, сервіси та технології » (м. Кіровоград, 25-27 квітня 2007 року), «Моделювання та комп'ютерна графіка» (м. Донецьк, 10-12 жовтня 2007 року), «Моделювання та комп'ютерна графіка» (м. Донецьк, 7-9 жовтня 2009 року).

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

Публікації. Основні результати дисертаційної роботи опубліковані в 10 наукових працях, з них 5 статей у виданнях, включених до переліку ВАК України, 5 публікацій у працях конференцій.

Структура та обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаних джерел, що складається з 97 найменувань та двох додатків. Повний обсяг дисертація становить 178 сторінок друкованого тексту, з них 135 сторінок основного тексту, містить 91 рисунок і 15 таблиць.

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

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

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

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

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

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

, (1)

де IPS -- швидкодія процесора, N_app -- кількість інструкцій, необхідна для обробки одного пакету, A - площа пристрою.

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

Рис. 1. Структура мережного процесора з загальною пам'яттю

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

. (2)

У разі якщо обробка не завершилася, то з імовірністю P_m,i () буде потрібно звернення до оперативної пам'яті за даними або кодом. Імовірність P_m,i залежить від інтенсивності звернень до ОЗП і імовірностей промаху кешів:

, (3)

де P_d,i -- імовірність звернень за даними, під час обробки пакету на i-му етапі конвеєра, P_dc,i -- імовірність промаху кеша даних, P_ic,i -- імовірність промаху кеша команд.

Рис. 2. Мережа СМО, моделююча мережний процесор із загальною пам'яттю

Імовірність P_d,i може бути розрахована як відношення звернень до ОЗП за час обробки одного пакету (N_d,i) до загальної кількості інструкцій, виконаних за час його обробки (N_prc,i):

. (4)

Після завершення звернення до ОЗП обробка пакета продовжується на тому ж етапі конвеєра, на якому вона була перервана для звернення до пам'яті. Всі етапи конвеєра використовують один модуль ОЗП. Оскільки імовірність переходу з i-го етапу конвеєра до ОЗП дорівнює P_m,i(1-P_f,i), то імовірність переходу пакету з ОЗП на i-й етап конвеєра (P_r,i) визначається за формулою:

. (5)

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

По завершенні обробки з імовірністю P_f,i () пакет передається наступному етапу конвеєра. Вихідний потік л₀P_f,n моделює вихідний потік оброблених пакетів.

Якщо вхідний потік пакетів для мережі СМО, представленої на рис. 2, розподілений за законом Пуассона з інтенсивністю л₀, то можна записати систему рівнянь для інтенсивностей потоків пакетів:

 (6)

де л_i () -- вхідні потоки до етапів конвеєра, а л_ram -- вхідний потік до блоку ОЗП.

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

Рис. 3. Структура мережного процесора з розподіленою пам'яттю



Рис. 4. Мережа масового обслуговування, моделююча мережний процесор з розподіленою пам'яттю

У запропонованій структурі в загальному блоці ОЗП зберігаються тільки дані, що оброблюються. Така структура більш продуктивна, ніж структура із загальною пам'яттю. На рис. 4 представлена мережа масового обслуговування, моделююча МП з розподіленою пам'яттю.

Ця модель відрізняється правилами взаємодії з пам'яттю під час обробки пакета. Мережний пакет з вхідного потоку з інтенсивністю л₀ надходить на перший етап конвеєра м₁ і виконується одна інструкція по його обробці. Після цього, з імовірністю P_f,1 обробка завершується, і пакет переходить на наступний етап конвеєра. Якщо цього не відбувається, то з імовірністю P_ic,1(1-P_f,1) виконання наступної інструкції зажадає звернення до ОЗП команд м_ins,1. Отримавши код команди, з імовірністю P_m,1 буде потрібно звернення до ОЗП за даними, якщо ж ці не потрібні, то з імовірністю (1-P_m,1) процесор перейде до виконання отриманої інструкції. Якщо ж така інструкція опинилася в кеші, і звернення до ОЗП команд не потрібно, то з імовірністю P_m,1(1-P_ic,1)(1-P_f,1) процесору потрібно звернення до ОЗП даних.

Імовірність звернення до ОЗП даних (P_m,i) визначається за формулою:

, (7)

де P_d,i -- імовірність того, що поточній інструкції потрібні дані, а P_dc,i -- імовірність промаху кеша даних.

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

. (8)

Крім описаних сценаріїв виконання команд на процесорі, існує імовірність того, що інструкції не потрібно ані звернення до ОЗП команд, ані звернення до ОЗП даних. Ця імовірність дорівнює (1-P_m,1)(1-P_ic,1)(1-P_f,1).

Об'єднавши перераховані сценарії виконання команд, отримуємо систему рівнянь для потоків в аналізованому мережному процесорі:

(9)

Ще одним способом зниження навантаження на блок ОЗП є використання в кожному обчислювальному ядрі кеша команд, достатньо великого для розміщення всього коду програми (див. рис. 5). Така структура може бути продуктивніше обох запропонованих раніше структур, але буде мати більшу площу за рахунок необхідності використання великого кешу.

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

(10)

Рис. 5. Структура мережного процесора з виділеним кешем

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

Для аналізу структур мережних процесорів використовувалася інтегрована методика, представлена на рис. 6.

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

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

Для аналізу роботи програми необхідно задати структуру процесора, параметри кеш-пам'яті і задати його вхідні параметри.

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

Рис. 6. Структура інтегрованої методики моделювання

Логічно програми в CommBench розділені на дві групи: програми, що обробляють тільки заголовки пакетів і програми, що обробляють дані, що передаються в пакеті.

До першої групи належать задачі фрагментації, маршрутизації, планування черг та моніторингу мережного трафіку. У другу групу потрапили програми роботи з медіа-даними (на прикладі JPEG), стисненим потоком (ZIP), виконання надлишкового кодування (REED) і шифрування даних (CAST).

Набір тестових програм у дисертації було розширено алгоритмом динамічної маршрутизації нового покоління AntNet. Цей алгоритм ґрунтується на мобільних агентах і показує кращі результати в порівнянні з класичними алгоритмами динамічної маршрутизації.

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

Після виконання імітаційного моделювання, отримані параметри використовуються для розрахунку характеристик мережного процесора. Характеристики системи розраховуються в два етапи: розрахунок продуктивності процесора (пакетів в секунду, PPS) і розрахунок його площі (кв. мм, A). Отримані значення в подальшому можуть бути використані як самостійно, так і для складання комплексних метрик.

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

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

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

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

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

З діаграм видно, що на задачах фрагментації (Frag), планування черг (DRR) і надлишкового кодування (REED) похибки, що вносяться моделюванням незначні. Для задачі шифрування (CAST) ставлення звернень до кешів під час обробки пакетів до загальної кількості звернень за весь час моделювання досягає 0.68 для кеша команд і 0.55 для кеша даних. Для задачі пошуку в маршрутної таблиці (RTR) це співвідношення коливається від 0.01 до 0.54, в залежності від кількості оброблених пакетів.

Для задач стиснення потоку (ZIP) і перетворення медіа-даних (JPEG) в силу їх структури неможливо відокремити роботу з файлами від обчислень, тому слід уникати їх використання при дослідженні мережних процесорів або ж переробити їх код і виділити обробку даних в окрему функцію.

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

Рис. 8. Залежність метрики PPS/A від розмірів кешів для задачі фрагментації (FRAG)



Рис. 9. Залежність метрики PPS/A від розмірів кешів для задачі планування черг (DRR)

На рис. 8 і 9 зображена залежність метрики PPS/A (1) від розмірів кешів команд та даних для задач фрагментації (FRAG) та планування черг (DRR) відповідно. Фрагментація виконується на маршрутизаторах, що розташовані на межі гетерогенних мереж з різними значеннями максимального розміру пакета (Maximum Transfer Unit, MTU). Вона необхідна в тих випадках, коли пакет не може бути переданий через мережу цілком й розбивається на більш дрібні частини.

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

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

Задача маршрутизації має більшу алгоритмічну складність і під час пошуку в таблиці маршрутів частіше звертається до зовнішньої пам'яті. Зміна метрики PPS/A для задачі маршрутизації показана на рис. 10. Тут пік досягається при кеші команд, який дорівнює 32 КБ та кеші даних розміром 8 КБ. Наведені результати були здобуті для одноядерного однопотокового процесора з роздільними кешами команд і даних. При збільшенні числа обчислювальних ядер або потоків, що підтримуються апаратно оптимальні значення можуть виявиться іншими.

Рис. 10. Залежність метрики PPS/A від розмірів кешів для задачі пошуку в таблиці маршрутизації (RTR)

На рис. 11 показані графіки залежності ефективності мережного процесора від числа обчислювальних ядер. Наведені дані були отримані для кешів команд та даних, що дорівнюють 1 КБ. З графіків видно, що для програм динамічної маршрутизації (AntNet), планування черг (DRR) та пошуку в маршрутній таблиці (RTR) оптимальним є число обчислювальних ядер, що дорівнює трьом. Ефективність процесора, що виконує фрагментацію, росте повільніше та досягає максимального значення при наявності десяти процесорних елементів. Найбільш трудомісткі програми групи обробки даних досягають максимальної питомої продуктивності при наявності п'яти та двох обчислювальних ядер для надмірного кодування (REED) та шифрування (CAST) відповідно.

Рис. 11. Вплив кількості обчислювальних ядер на питому продуктивність мережного процесора

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

Таблиця 1. Найбільш продуктивні структури МП

Програма	Параметри мережного процесора	Критерії ефективності
	Кіл-ть кластерів	Кіл-ть ядер	Кіл-ть потоків	Кеш команд, КБ	Кеш даних, КБ	PPS	PPS/A
FRAG	1	16	1	1	4	258173	1048,73
DRR	1	4	2	1	8	521875	5469,98
RTR	1	16	1	32	16	824734	921,00
REED (enc)	1	16	1	1	2	6481	29,87
REED (dec)	1	16	1	1	4	4066	16,52
CAST (enc)	1	16	1	16	8	45248	84,78
CAST (dec)	1	16	1	16	8	44968	83,75
AntNet	1	6	1	4	8	901985	6329,84

На рисунку 12 наведено порівняння максимальної продуктивності МП трьох різних архітектур в залежності від тактової частоти обчислювальних ядер. Видно, що використання великого кешу для коду команд дає максимальну продуктивність при великих тактових частотах, але до частоти 350 Mhz різниця між великим кешем команд та розподіленим ОЗП незначна.

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

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



Рис. 13. Порівняння середнього часу обробки пакету в залежності від інтенсивності вхідного потоку

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

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

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

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

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

Висновки

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

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

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

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

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

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

Проведено дослідження роботи мережного процесора з розподіленою пам'яттю. Показано, що виділення окремого блока пам'яті для коду кожного етапу конвеєра на 23% збільшує продуктивність системи та зменшує час обробки пакету в 4 рази у порівнянні зі структурою з загальною пам'яттю.

Проведено дослідження роботи мережного процесора з кешем команд кожного обчислювального ядра достатньо великим для розміщення всього коду програми. Показано, що така структура на 73% продуктивніше структури з загальним ОЗП і в 11 разів зменшує час обробки пакету.

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

Результати дисертаційного дослідження використано у науково-виробничому підприємстві ТОВ “АМІ” (м. Донецьк) при розробці підсистеми маршрутизації комп'ютерних мереж; в науково-дослідних роботах Донецького національного технічного університету №Д-1-05 «Розвиток теорії мережних інформаційних технологій розподіленого моделювання та синтезу цифрових систем на програмуємих пристроях» (номер держ. реєстрації 0105U002288) та № Д-1-08 «Розвиток теорії синтезу і розподіленого моделювання високопродуктивних проблемно-орієнтованих обчислювальних систем з програмованими НВІС» (номер держ. реєстрації 0108U001959); у навчальному процесі при читанні лекцій з курсів “Комп'ютерні мережі”, “Теорія та організація розподіленої обробки даних в комп'ютерних мережах” та “Архітектура комп'ютера”.

Список опублікованих робіт по темі дисертації

1. Ладиженський Ю.В. Эффективность реализации протокола маршрутизации AntNet на сетевых процесорах [Текст] / Ю.В. Ладыженский, В.И. Грищенко // Наукові праці Донецького Національного технічного університету. Серія „Інформатика, кібернетика і обчислювальна техніка” (ІКОТ-2007). -- Вип. 8 (120). -- 2007. -- C. 169--178.

2. Грищенко В.И. Исследование архитектуры кэша сетевых процессоров [Текст] / В.И. Грищенко, Ю.В. Ладыженский // Науково-технічний журнал „Радіоелектронні і комп'ютерні системи”. -- Вип. 6 (25). -- С. 186--192.

3. Ладиженський Ю.В. Влияние политики замещения записей в кэше на производительность сетевого процессора [Текст] / Ю.В. Ладыженский, В.И. Грищенко // Наукові праці Донецького національного технічного університету. Серія: „Обчислювальна техніка та автоматизація”. -- Вип. 12 (118). -- Донецьк ДонНТУ, 2007. -- С. 114--119.

4. Грищенко В.И. Моделирование маршрутизаторов на многоядерных сетевых процессорах [Текст] / В.И. Грищенко, Ю.В. Ладыженский // Научные труды Донецкого национального технического университета. Серия «Информатика, кибернетика и вычислительная техника» (ИКВТ-2010). -- Вып. 12 (165). -- Донецк: ГВУЗ «ДонНТУ», 2010. -- С. 169--176.

5. Грищенко В.И. Исследование влияния раздельной памяти на производительность многоядерного сетевого процессора [Текст] / В.И. Грищенко, Ю.В. Ладыженский // Наукові праці Донецького національного технічного університету. Серiя «Проблеми моделювання та автоматизації проектування» (МАП-2011). -- Вып. 9 (179). -- Донецьк: ДонНТУ. -- 2011. -- С. 293--303.

6. Ладыженский Ю.В. Программирование процессоров обработки пакетов в компьютерных сетях [Текст] / Ю.В. Ладыженский, В.И. Грищенко // Матеріали міжнародної науково-практичної конференції „Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій”. -- м. Запоріжжя, 2006. -- 13-15 квітня. C. 159-161.

7. Ладыженский, Ю.В., Моделирование сетевых процессоров пакетной обработки данных [Текст] / Ю.В. Ладыженский, В.И. Грищенко // Материалы международной научно-практической конференции «Интернет -- Образование -- Наука - 2006». -- г. Виница, 2006. -- 10--14 октября. -- Т. 2. -- С. 417--422.

8. Грищенко В.И. Моделирование работы приложений на сетевых процессорах. [Текст] / В.И. Грищенко, Ю.В. Ладыженский // Материалы международной научно-практической конференции «Моделирование и компьютерная графика 2007». -- г. Донецк. -- 10-12 октября. -- С. 167--173.

9. Грищенко В.И. Использование сетевых процессоров для решения задачи маршрутизации в компьютерных сетях [Текст] / В.И. Грищенко, Ю.В. Ладыженский // Матеріали міжнародної науково-практичної конференції „Інформатика та комп'ютерні технології 2007”, 11-13 грудня. -- м. Донецьк, 2007. -- С. 97--99.

10. Грищенко В.И. Оптимизация методики моделирования кэша сетевых процессоров [Текст] / В.И. Грищенко, Ю.В. Ладыженский // Моделирование и компьютерная графика: Материалы 3-й международной научно-технической конференции, г. Донецк, 7-9 октября 2009 г. -- Донецк: ДонНТУ, Министерство образования и науки Украины, 2009. -- C. 249--254.

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

...