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

      Велика  кількість роботи по розробці масштабування  обчислинь алгоритму SOM була зроблена за останні роки. Взагалі кажучи існує два основних підходи, якими є розбиття гратки (map-partitioning, MP) та розбиття даних (data-partitioning, DP).

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

      В DP, вхідні дані розподілені поміж потоками, так, що кожен потік містить частину вхідних даних та проганяє її на своїй копії гратки. Як бачимо цей підхід не вимагає частої синхронізації, таким чином це є перевагою над MP. Проте такий підхід не відповідає формулі оновлення, що змушує використовувати його із варіаціями SOM, зоокрема batch SOM. Та навіть попри це batch SOM не є популярним методом, із-за двох основних причин:

         1. Він вимагає щоб усі вхідні вектори були наперед відомими, що не є завжди можливо.
         2. Насправді дуже важко отримати добре структуровану карту на відміну від класичного алгоритму.

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

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

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

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


Такий підхід дає помітні покращення коли гратка є дуже виликих розмірів.

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInEmail this to someone