Optimization of parallel perceptron for central processing units

The problem of efficient implementation of multi-layered perceptron is examined for central processing units of the type of i686. Facilities of optimizationby speed of tasks of computation and learning of perceptron on these processors with the use of multithreading and parallel instructions are off...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
Hauptverfasser:	Doroshenko, A.Yu., Kosan, O.S.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2025
Schlagworte:	UDC 004.8 004.051
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/813
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-813
record_format	ojs
resource_txt_mv	ppisoftskievua/91/1a4c67f6c42c9ebc63f7beb5e384e591.pdf
spelling	pp_isofts_kiev_ua-article-8132025-08-29T19:53:15Z Optimization of parallel perceptron for central processing units Оптимізація паралельного перцептрона для центральних процесорів Doroshenko, A.Yu. Kosan, O.S. UDC 004.8, 004.051 УДК 004.8, 004.051 The problem of efficient implementation of multi-layered perceptron is examined for central processing units of the type of i686. Facilities of optimizationby speed of tasks of computation and learning of perceptron on these processors with the use of multithreading and parallel instructions are offered.Prombles in programming 2011; 3: 23-29 Розглядається проблема ефективної реалізації багатошарового перцептрона для центральних процесорів класу i686. Запропоновано методику оптимізації за швидкодією процедур обчислення і навчання перцептрона на цих процесорах із застосуванням багатопоточності та використання паралельних інструкцій.Prombles in programming 2011; 3: 23-29 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-29 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/813 PROBLEMS IN PROGRAMMING; No 3 (2011); 23-29 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2011); 23-29 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2011); 23-29 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/813/865 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-08-29T19:53:15Z
collection	OJS
language	Ukrainian
topic	UDC 004.8 004.051
spellingShingle	UDC 004.8 004.051 Doroshenko, A.Yu. Kosan, O.S. Optimization of parallel perceptron for central processing units
topic_facet	UDC 004.8 004.051 УДК 004.8 004.051
format	Article
author	Doroshenko, A.Yu. Kosan, O.S.
author_facet	Doroshenko, A.Yu. Kosan, O.S.
author_sort	Doroshenko, A.Yu.
title	Optimization of parallel perceptron for central processing units
title_short	Optimization of parallel perceptron for central processing units
title_full	Optimization of parallel perceptron for central processing units
title_fullStr	Optimization of parallel perceptron for central processing units
title_full_unstemmed	Optimization of parallel perceptron for central processing units
title_sort	optimization of parallel perceptron for central processing units
title_alt	Оптимізація паралельного перцептрона для центральних процесорів
description	The problem of efficient implementation of multi-layered perceptron is examined for central processing units of the type of i686. Facilities of optimizationby speed of tasks of computation and learning of perceptron on these processors with the use of multithreading and parallel instructions are offered.Prombles in programming 2011; 3: 23-29
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/813
work_keys_str_mv	AT doroshenkoayu optimizationofparallelperceptronforcentralprocessingunits AT kosanos optimizationofparallelperceptronforcentralprocessingunits AT doroshenkoayu optimízacíâparalelʹnogoperceptronadlâcentralʹnihprocesorív AT kosanos optimízacíâparalelʹnogoperceptronadlâcentralʹnihprocesorív
first_indexed	2025-09-17T09:23:50Z
last_indexed	2025-09-17T09:23:50Z
_version_	1850409902538752000
fulltext	Паралельне програмування УДК 004.8, 004.051 А.Ю. Дорошенко, О.С. Косань ОПТИМІЗАЦІЯ ПАРАЛЕЛЬНОГО ПЕРЦЕПТРОНА ДЛЯ ЦЕНТРАЛЬНИХ ПРОЦЕСОРІВ Розглядається проблема ефективної реалізації багатошарового перцептрона для центральних процесо- рів класу i686. Запропоновано методику оптимізації за швидкодією процедур обчислення і навчання перцептрона на цих процесорах із застосуванням багатопоточності та використання паралельних ін- струкцій. Вступ На сьогодні актуальними залиша- ються швидкісні обчислення нейромереж (НМ) у задачах класифікації та розпізна- вання зображень великого розміру, що ви- користовуються, зокрема, в задачах ком- п’ютерного зору. Для ефективного функ- ціонування нейронних мереж існує можли- вість створити спеціалізовані рішення для різнотипних процесорів з найширшим ви- користанням їх можливостей. 22 © А.Ю. Дорошенко, О.С. Косань, 2011 ISSN 1727-4907. Проблеми програмування. 2011. № 3 Нейронна мережа типу багатошаро- вого перцептрона складається з елемен- тарних структурних одиниць, що назива- ються нейронами [1, 2] (рис. 1). Рис. 1. Окремий нейрон нейромережі Кожен нейрон має декілька входів (x1,..,xn), на які подаються дійсні значення. Кожна вхідна величина домножується на відповідну їй величину вагового коефіціє- нта (w1,..,wn). Далі кожен частинний добу- ток подається на суматор і на обрану акти- ваційну функцію нейрона. У цій роботі ви- користана активаційна функція – однопо- лярний сигмоїд, який був обраний через високу обчислювальну простоту його по- хідної, що обчислюється, наприклад, як значення виразу f(sum) · (1 – f(sum)). В реа- лізації активаційна функція може бути за- мінена на біполярну (рис. 2) для кращої збіжності навчання [1]. Рис. 2. Біполярна активаційна функція нейрона – сигмоїд Існує велика кількість програмних реалізацій нейромереж для роботи на центральних процесорах, але більшість з них не пристосовані для виконання в бага- топоточному режимі, або не оптимізовува- лись спеціально для високої ефективності. Частина з розглянутих існуючих бібліотек для роботи з нейронними мережами не по- вністю використовують обчислювальні по- тужності центральних процесорів, такі як SIMD-інструкції. У табл. приведені основ- ні переваги та недоліки оглянутих бібліо- тек. У цій роботі проводиться дослідження ефективності виконання задачі обчислення багатошарового перцептрона на мульти- ядерних процесорах та пропонуються ре- комендації щодо методики їх оптимально- го використання. Для досягнення макси- мальної гнучкості рішення, задача розгля- дається на найнижчому рівні розпарале- лювання, без використання сторонніх біб- ліотек, таких як OpenMP та Intel TBB [3]. Паралельне програмування Таблиця Назва бібліотеки Багато поточність Набір типів архітектур мереж Платформи Ліцензія та код Швидкість FANN [4] Ні Всі загальні Будь-яка LGPL, Відкритий Висока Encog [5][6] Так Основні Java та .NET (Windows) LGPL, Відкритий Висока Flood [7] Ні Перцептрон Будь-яка Відкритий Висока JOONE [8] Так Основні Java Відкритий Середня Neuroph [9] Ні Більшість загальних Java Відкритий Низька 1. Постановка задачі Для ефективного розв’язання по- ставленої задачі необхідно врахувати осо- бливості сучасних центральних процесо- рів, такі як багатопоточність та можливості SIMD-інструкцій для прискорення обчис- лення нейронної мережі. Додатково важ- ливо враховувати фактори, що потенційно можуть вплинути на зниження ефективно- сті обчислень, а саме: часті виконання умовних операторів, відсутність вирівню- вання даних, неструктурованість та непо- слідовність даних, конкуренція за ресурси і т. і. Для цього необхідно проводити ана- ліз параметрів задачі, при яких викорис- тання тих чи інших засобів оптимізації призводять до прискорення виконання (або уповільнюють) програму. Експериментальну задачу для до- слідження ефективності виконаємо споча- тку в вигляді спрощеної задачі обчислення одношарового перцептрона на декількох процесорах та з окремими алгоритмічними шляхами для однопоточного та багатопо- точного режиму. Результати досліджень наведені далі. 1. Характерні низькі затрати на си- нхронізацію потоків при правильному групуванні задачі, але неможливо усунути недолік недостатньої пропускної здатності пам’яті для високих розмірностей задачі. Досягнуто прискорення від 160 % (середні розмірності) до 125 % (високі розмірності) за рахунок другого ядра. Очевидно, що при зростанні розмірності задачі, для кое- фіцієнтів нейронів виявилось недостатньо вільного місця кеш-пам’яті. 2. Створення потоків для малороз- мірної задачі (менше 210 нейронів на шар) (32x32) не доцільно через затрати часу операційної системи (ОС). Для ОС Windows створення потоку займає більше 2 мкс, активізація та зміна параметрів та- кож вимагають частих затримок під час переключення в режим ядра. 3. Повторний запуск потоку обчис- лення дозволяє зберегти дані кеш-пам’яті та знизити звернення до ОЗП. З урахуван- ням цього, доцільно використовувати пул потоків. 4. Відмова від планування потоків ОС призводить до незначного (~3 %) під- вищення продуктивності обчислень. З ін- шого боку, жорстка прив’язка потоку до процесора (за рахунок Affinity Mask) не доцільна на дрібних задачах з урахуванням часових витрат на її здійснення. Також жорстка прив’язка призводить до знижен- ня надійності програми та стійкості ре- зультату – у випадку блокування одного ядра, програма може перейти в тривалий цикл очікування. 5. Використання суперскалярних «широких» інструкцій розряду Streaming SIMD Extensions (SSE) призводить до при- скорення на 20 – 300 %, але потребує спе- ціальних методик вибірки та збереження даних, що вимагає створення альтернатив- ного алгоритмічного кодового шляху). Ви- користання при компіляції додатково SSE2 та SSE3 не вплинуло на показники швид- кодії. Для SSE вкрай необхідне вирівню- вання та послідовність подачі даних, що 23 Паралельне програмування виключає використання об'єктної моделі у коді обчислення програми. 6. Зберігання проміжного варіанта обчислення похідної сигмоїди для його повторного використання не завжди вигід- ніше його повторного розрахунку, оскіль- ки використовується проста функція акти- вації, та похідна що залежить від неї. 7. Використання табличних функ- цій (для сигмоїди) у даній задачі виправ- далося тільки на процесорі Xeon з HyperThreading та дало приріст у 10 – 15 %, в усіх інших випадках дало гірший резуль- тат ніж розрахунок точного значення сиг- моїди. Причина може полягати в перена- вантаженості шини пам'яті та критичності кеш пам’яті для корисних даних. Виклю- чення на серверному процесорі можна по- яснити його зниженими арифметичними можливостями. 8. Відсутність вирівнювання даних унеможливлює ефективну роботу програ- ми, оскільки вона необхідна не тільки для виконання команд SSE, але і для реалізації ефективної синхронізації (spinlock). Порівняння ефективності обчис- лень задачі на різних конфігураціях пока- зано на рис. 3. Складність задачі в даному випадку – розмір сторони матриці вхідного зображення (наприклад, останнє значення становить 14×14 = 196 входів НМ). З гра- фіка видно, що найбільший час обчислен- ня був отриманий в однопоточній програ- мі. Використання SSE значно знижує за- трати часу на обчислення. Використання SSE в декількох потоках одночасно вияви- лось ефективним, але витрати на створен- ня потоків на таких розмірностях призвели до того, що багатопоточна програма пра- цювала загалом повільніше, ніж одно- поточна. При використанні пулу потоків вдалось компенсувати ці витрати. Рішення проблеми підбору параме- трів може заключатись у створенні профі- лю продуктивності процесора для задачі з різними коефіцієнтами на базі попередньо- го (тестового) обрахунку задачі з різними параметрами. Під час тесту продуктивнос- ті визначаються моменти, коли включення тих чи інших технологій призводить до зростання продуктивності. Рис. 3. Залежність часу обчислення тестової задачі розрахунку одношарового перцептрона від складності задачі 24 Паралельне програмування В даній реалізації встановлені жор- сткі пороги включення додаткового потоку (не менше 64-х нейронів). На рис. 4 пока- зано схематичне зображення задачі для двох ядер. На вході довільна кількість вхідних нейронів (доповнена до кратної 4 для вирі- внювання даних), на виході – довільна кі- лькість вихідних нейронів. Мережа повнозв’язна, всі вагові ко- ефіцієнти для всієї мережі виділені в ди- намічній пам’яті за один раз за попереднім розрахунком їх ємкості з урахуванням ви- рівнювання. З рис. 4 також видно, що для кожного потоку відводиться кількість ней- ронів, кратна 4 (вимога SSE). Розподілення нейронів кожного шару між потоками про- водиться рівномірно, у випадку неможли- вості поділити рівно, перевага надається не першому потоку, оскільки він додатково завантажений синхронізацією усіх потоків. Математично процес обчислення вихідних значень кожного шару буде представляти добуток вектора вихідних значень попереднього шару X та матриці вагових коефіцієнтів W для кожного ней- рона цього шару. W10 W11 W12 Входи Асоціативні (приховані) шари S \| Y S \| Y S \| Y S \| Y S \| Y W10 W12 W13 W 1m Вихідний шар W n3 Wn4 Wn5 S \| Y S \| Y W00 W 02 Кількість шарів S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y S \| Y X0 X1 X3 X2 Y0 Y1 Y2 Y3 Ym Yf1 Yf2 W00 W22 W33 Xn Wn6 Xf1 Xf2 Рис. 4. Програмне розбиття задачі для декількох ядер (показані не всі зв’язки між нейронами) 25 Паралельне програмування Такий метод розпаралелювання за рядками (рис. 5) може бути виправданий, оскільки таким чином для кожного з k процесорів утворюється максимально дов- га послідовність безперервних даних, дов- жиною n, та мінімальна кількість синхро- нізуючих операцій (максимальна незалеж- ність даних), необхідна по закінченню q рядків. Також, таке розділення потребує повного дублювання вектора X для кожно- го з ядер. Оскільки вектор X, при збільшенні кількості входів зростає лінійно, а матриця вагових коефіцієнтів – квадратично, то об- раний метод розділення буде мати мініма- льний негативний вплив на ефективність обчислень за умови, що весь вектор X по- вністю розміщений в кеш пам’яті даних. В іншому випадку доцільно використовувати блочне розбиття або розбиття за стовпця- ми матриці W. Процес навчання нейронної мережі методом зворотного розповсюдження по- милки включає в себе етап обчислення і корекції вагових коефіцієнтів мережі. Для прискорення останнього, доцільно створити варіант функції обчислення, що розраховує також і похідні виходів. Для фантомних вхідних та вихідних нейронів (що створюються для вирівнюван- ня), виділяється додаткова пам’ять у масиві вагових коефіцієнтів, але участі в розрахунку вони не приймають (крім варіанта де викори- стовується SSE, тоді можна обрати викори- стання надлишкових нейронів). У даній реалізації для синхронізації використовується механізм подій (об’єкт Event для синхронізації в ОС Windows [10]). Оскільки одиниці рядка мають одна- кову обчислювальну ємність, то ефектив- ність обчислення буде залежати від одно- часності початку та закінчення розрахунку. Для оптимізації SSE використову- ється ручний розподіл змінних вектора су- ми s (s0..s3) – оптимізатор компілятора са- мостійно додає інструкції SSE де це мож- ливо. Арифметичні операції перегруповані так, щоб мати мінімальну залежність операндів. Рис. 5. Представлення даних одного шару та їх розділення між потоками 26 Паралельне програмування 2. Результати експериментів Обчислення здійснювались на сис- темі з наступною конфігурацією: процесор – AMD Phenom FX-5000 (2.42 ГГц, 4 ядра, 2 Мб L2 кеш, 6 Мб L3 кеш), обсяг оперативної пам’яті – 2 Гб; ОС – Windows XP SP3; Результат швидкості обчислень для різних задач показано на рис. 6. З якого видно, що однопоточна програма, яка ви- користовує SSE має значну перевагу над простою однопоточною програмою. Вод- ночас, багатопоточна програма, що вико- ристовує SSE, має низку перевагу від до- даткових ядер, що може бути пояснено обмеженою пропускною здатністю пам’яті [11]. Код експерименту розміщений у [12]. Ураховуючи результати експериме- нтів можна запропонувати ряд рекоменда- цій: - попередньо проводити тест розпа- ралелювання задачі у спрощеному вигляді; - у залежності від того, чи буде про- грама конкурувати за ресурси з іншими програмами, а також беручи до уваги енер- гозбереження, обираємо спосіб синхроні- зації потоків – можливостями операційної системи (мьютекси, семафори та події), чи спін-лок (англ. spin-lock) синхронізацію вбудованими (intrinsic) функціями. Як пра- вило, спін-лок синхронізація більш ефек- тивна за швидкодією [10, 13], оскільки не вимагатиме виклику функцій ядра, але більш енерговитратна, оскільки ядра очі- кують сигнал синхронізації у циклі; - при розділенні задач для кожного потоку необхідно розділяти оброблювані дані так, щоб кожен потік зберігав макси- мальну кількість даних в кеш пам’яті, та не заміщував їх при кожній операції; - використовувати інструкції SSE та інші, в тих випадках, коли можна гаранту- вати кратність вхідних даних до розміру «широкого» регістру. У випадках, коли ро- змірності не збігаються, необхідно про- Рис. 6. Залежність часу обчислення задачі розрахунку багатошарового перцептрона від складності задачі 27 Паралельне програмування вести доповнення (до 32 байт, у випадку SSE) та вирівнювання вхідних даних (на адресу кратну 32 байтам), при чому забез- печити відсутність впливу від обчислення вирівнювальних даних (найчастіше дося- гається зануленням); - розгортати цикли, в тому числі ча- стково, коли за рахунок цього можливо зменшити витрати на повторне обчислен- ня, або значно перегрупувати дані та поря- док операцій над ними. При цьому необ- хідно враховувати, що надмірне розгор- тання циклу (більше 16 – 32 ітерацій) при- зведе до збільшення розміру коду програ- ми, внаслідок чого може знизитись її вміс- тимість у кеші інструкцій і, як наслідок, знизиться швидкодія; - у випадку, коли не використову- ються асемблерні вставки, для досягнення застосування компілятором широких ко- манд та паралельних конвеєрів сучасних процесорів у результаті оптимізації, необ- хідно групувати порядок операцій над да- ними так, щоб команди з взаємонезалеж- ними операндами йшли підряд, а їх дані знаходились згрупованими та йшли послі- довно, що частково протирічить концепції ООП, де об’єкт зберігає самодостатність, та зберігає різнорідні дані поряд; - для зниження фрагментованості пам’яті доцільно виділяти пам’ять для всіх динамічних буферів задачі, єдиним систе- мним викликом, коли це можливо; - використовувати вбудовувані фун- кції для невеликих операцій, та вбудовані (intrinsic) функції для зниження витрат на системний виклик; - при обробці великих обсягів даних використовувати табличні функції тільки тоді, коли її значення має значну арифме- тичну складність (більше 5 – 10 арифмети- чних операцій, що може бути досягнуто шляхом ускладнення активаційної функ- ції), оскільки таблиця значень буде конку- рувати з даними за спільні ресурси – кеш пам’ять та пропускну здатність шини пам’яті. Методика Підсумовуючи вищевказане можна сформулювати наступні пункти методики оптимізації за ефективністю процедур обчислення та навчання багатошарового пе- рцептрона на мультиядерних процесорах. 1. Створити для кожного ядра від- повідну нитку обчислень, що бере на себе задачу розрахунку вихідного значення рів- номірно розділених між ядрами і послідо- вно розміщених нейронів з кожного шару. Розділити рівномірно між ядрами нейрони кожного шару, при цьому розділення мат- риці вагових коефіцієнтів здійснювати за рядками. Всередині множити елементи ря- дка та вхідного вектора з використанням інструкцій SSE, при цьому доцільно розго- ртати цикл на 4 – 16 операцій (1 – 4 інст- рукції SSE). Для великих розмірностей синхронізацію потоків здійснювати мето- дом spinlock, для великих – через механізм подій. 2. Для процедури навчання необ- хідне створення окремих потоків корекції коефіцієнтів, а також процедури обчис- лення з модифікованим алгоритмом, що обчислює необхідні значення похідних ви- ходів кожного шару. Дана методика може бути також використана для оптимізації нейронних мереж і для інших архітектур. Висновки Досліджено та розроблено методи- ку підвищення ефективності програмної реалізації багатошарового перцептрона на багатоядерному центральному процесорі. Для підвищення ефективності обчислень перевірено різнотипні засоби оптимізації, найефективнішим з яких виявилося вико- ристання SIMD-інструкцій. При комбіну- ванні всіх методів було виявлено, що для ефективного обчислення задачі великих розмірностей необхідна висока пропускна здатність пам’яті. 1. Комашинский В.И., Смирнов Д.А. Нейрон- ные сети и их применение в системах управления и святи. – М.: Горячая линия- Телеком, 2002. – 94 с. 2. Хайкин Саймон. Нейронные сети: полный курс, 2-е изд., испр.: Пер. С англ. – М.: ООО Вильямс, 2006. – 1104 с. 3. Rainders James. Intel Threading Building Blocks. – Sebastopol: O’Reilly Media, Inc., 2007. – 305 с. 4. FANN http://leenissen.dk/fann/wp/ 28 Паралельне програмування 5. Encog http://www.heatonresearch.com/encog 6. Порівняльний тест нейромереж http://www.codeproject.com/KB/recipes/benc hmark-neuroph-encog.aspx (3/6/2010) 7. Flood http://www.cimne.com/flood/ 8. JOONE https://sourceforge.net/projects/joone/ 9. Neuroph http://neuroph.sourceforge.net/ 10. Рихтер Джеффри, Кристоф Назар. Windows via C/C++. Программирование на языке Visual C++. – СПб.: Питер, 2009. – 896 с. 11. Breshears Clay. The Art of Concurrency. – Sebastopol: O’Reilly Media, Inc., 2009. – 287 с. 12. Код бібліотеки та програми експерименту, [archive] URL http://endrobene.org/download .php?f=xnn_exp_2.zip (10 травня 2011) 13. Herlihy Maurice, Shavit Nir. The Art of Multiprocessor Programming, Morgan Kaufmann Publishers, 2008. – 508 с. Отримано 19.05.2011 Про авторів: Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, завідувач відділу теорії комп’ютерних обчислень, Косань Олег Станіславович, студент 5-го курсу магістратури. Місце роботи авторів: Інститут програмних систем НАН України, e-mail: dor@isofts.kiev.ua, Національний технічний університет України «КПІ», 03056, Київ, проспект Перемоги, 37. Тел.: 068 5993012, e-mail: jscythe@gmail.com 29 Вступ 1. Постановка задачі 2. Результати експериментів Методика Висновки

Optimization of parallel perceptron for central processing units

Institution

Ähnliche Einträge