Проект
по Системи за Паралелна Обработка
Паралелен Алгоритъм за пресмятане на Детерминанта на матрица
Изготвил:
Бойко Караджов
Ръководител:
ас. Христо Христов
Проверил: ........................
(ас. Христо Христов)
АБСТРАКТНО
Матриците се използват постоянно в моделирането на много различни типове данни като графи, игри и невронни мрежи. Детерминантата на една матрица дава много информация за данните в нея (примерно ако е равна на 0 знаем, че векторите, от които е съставена са линейно зависими). Затова пресмятането на детерминанта на матрица е нещо, което се налага често в най-различни математически проблеми. Пресмятането на детерминанта обемна операция и изисква много изчисления. Съвременните изчислителни системи работят паралелно и се нуждаем от подходящ алгоритъм за да използваме наличните ресурси.
-
Въведение
Алгоритъмът, който ще предложа използва адюнгирани количества. За матрица N x N трябва да изчисли детерминантите на N на брой матрици (N – 1) x (N – 1):
Като за матрица 2x2 вече използва директна формула:
По този начин за последователно изчисление сложността на алгоритъма е o(n!). Всяко адюнгирано количество може да бъде изчислено независимо от останалите, което дава възможност за очевидна паралелизация. Синхронизация е необходима само на края когато трябва получените резултати от адюнгираните количества да се редуцират в едно число – детерминантата. Алгоритъмът е следния:
-
Всяка нишка получава индекс и знае колко е общият брой на нишките.
-
Започва изчислението на адюнгирано количество с премахната колона от матрицата с индекс – равен на индекса на матрицата.
-
Когато завърши - увеличава индекса си с броя на нишките и преминава към стъпка едно ако индексът и не превишава броя на колоните на матрицата.
-
Изчаква всички нишки да приключат работа.
-
Редуцира резултатите им в крайният резултат.
-
Анализ
Синхронизация се прави само в края, което прави алгоритъмът много чист. Проблеми са, че отделните задачи са много големи и някои нишки може да изостанат повече от другите, при което може някои изчислителни ядра да останат в режим на изчакване. Освен това когато броят на нишките не е кратен на броя на колоните на матрицата в края работят само нишки равни на остатъка при делението на брой колони на матрицата / броя на нишките.
Идея: по-добър подход би бил да се работи по формулата на Лабниц като се генерират пермутации на елементите на матрицата и така всяка пермутация може да се изчисли независимо, изчисленията ще са разделени на много повече на брой много по-малки части.
-
Експеримент
Разработено е проложение на Java по горе описания алгоритъм. За експеримента ще се изчислява детерминанта на матрица с размерност 11 х 11. Спрямо броя нишки ще видим времето необходимо за изчисление (T) и следните два индикатора:
S(t) = T(1) / T(t)
E(t) = S(t) / t , където t е брой нишки.
Сподели с приятели: |