A NEW APPROACH TO CONSTRUCTING PARALLEL ALGORITHMS


A new approach to constructing parallel algorithms

Natela Archvadze, Merab Pkhovelishvili, Lia Shetsiruli

The traditional parallel algorithms of data processing based on method: (for some principal the number of cores, a speed of processing etc.) separate all information which should be processed into parts and then process each part separately on a different cores (or processor).
It takes quite a long time and is not always an optimal solution to separate into a parts. It’s impossible to bring to minimum a standing of cores. It’s not always possible to find optimal choice (or changing algorithm during execution).
The algorithms provided by us have the main principal that the processing by the cores should be performed in parallel and bring to minimum the stay of cores.
In the article are reviewed two algorithms working according to this principal “smart-delay” and the development of multiplication of matrix transposed ribbon-like algorithm.








ახალი მიდგომა პარალელური ალგორითმების ასაგებად


ახალი მიდგომა პარალელური ალგორითმების ასაგებად
ნათელა არჩვაძე, მერაბ ფხოველიშვილი, ლია შეწირული
ტრადიციულად, მონაცემთა დამუშავების პარალელური ალგორითმები ეფუძნება ორ მეთოდს: რომელიღაც პრინციპის მიხედვით (მაგალითად, ბირთვების რაოდენობის, თითოეულ პროცესორზე ძირითადი ოპერაციების შესრულების დროს და სხვ.) დაიყოს მთლიანი წარმოდგენილი ინფორმაცია ნაწილებად და შემდეგ თითოეული ნაწილი დამუშავდეს ცალკეულ ბირთვზე (ან პროცესორზე).
ინფორმაციის ნაწილებად დაყოფას სჭირდება საკმაოდ დიდი დრო და ეს პროცესი ყოველთვის არ ხდება ოპტიმალურად. კომპიუტერის ბირთვების მოცდენა უნდა იყოს მინიმუმამდე დაყვანილი. ყოველთვის როდი ხდება ოპტიმალური დაყოფის შერჩევა (ან/და ალგორითმის შეცვლა მუშაობის დროს).
ჩვენს მიერ შემოთავაზებული პარალელური ალგორითმის ძირითადი პრინციპია: მონაცემთა დაყოფა ნაწილებად და ბირთვებზე დამუშავება უნდა მოხდეს პარალელურად, რითაც ბირთვების მოცდენა მინიმუმამდე იქნება დაყვანილი.
სტატიაში განხილულია ამ პრინციპზე მოქმედი ორი ალგორითმი-დახარისხების (“Small Delay”) და მატრიცების გამრავლების ტრანსპონირებული ლენტური ალგორითმის განვითარება.