Irakli Koiava

     იგივე ფასის GPU- ს თუ შევადარებთ CPU- ს FLOPS-ებით(მცოცავმძიმიან რიცხვებზე ოპერაციები წამში) ვნახავთ, რომ GPU შესაძძლოა 10-ჯერ ჯობნიდეს CPU- ს(რასაც საკმაოდ ხშირად აკეთებენ მომხმარებლისთვის თვალის ასახვევად), თუმცა განსხვავებული არქიტექტურის გამო  CPU და GPU -ს შედარება FLOPS- ებით არაა გამართლებული. მათი უკეთ შედარება რომ შევძლოთ განვიხილოთ ამ პროცესორების არქიტექტურა.         CPU -ებს აქვთ მძლავრი ბირთვები( 2.0-3.0GHz და მეტი) და ასევე აქვთ ბირთვებზე SIMD რეგისტრები, რომლებიც ერთ პროცესორულ ციკლზე მრავალ მონაცემზე ერთი ინსტრუქციის შესრულების საშუალებას იძლევა. SIMD რეგისტრების სიგანე შეზღუდულია, მაგალითად თანამედროვე პროცესორებში შესაძლებელია ოპერაციები შესრულდეს 4, 8, 16 float -ზე ერთდროულად. ასევე CPU- ები გამოირჩევიან რამოდენიმე დონიანი კეშებით, რომლებიც ოპერატიული მეხსიერებიდან პროცესორის რეგისტრებში ინსტრუქციებისა და მონაცემების გადაცემას აჩქარებს. თანამედროვე პროცესორებს ასევე აქვთ ბევრი შიდა ოპტიმიზაცია (როგორიცაა მაგალითა...

branchless abs function         მოდულის გამოთვლის ფუნქცია არის ერთ-ერთი ყველაზე ხშირად გამოყენებადი ფუნქცია სხვადასხვა ტიპის გამოთვლების დროს, შესაბამისად ისეთი აპლიკაციებისთვის, რომელთათვისაც წარმადობა ძალიან მნიშვნელოვანია, მნიშვნელოვანია ასევე ამ ფუნქციის ოპტიმალური გადაწყვეტა. ფუნქციის ყველაზე მარტივი იმპლიმენტაცია ასე გამოიყურება : int abs ( int value ) {         if ( value < 0 )                   return - value ;         return value ; }          პროგრამულ კოდში დამატებითი განშტოებები გარკვეული ტიპის გამომთვლელი მოწყობილობებისათვის, მაგალითად GPU-სთვის, მკვეთრად ართულებს გამოთვლით პროცესს და საბოლოოდ ამცირებს წარმადობას. float -ის შემთხვევაში ჩვენ ვიცით, რომ ყველაზე მაღალი ბიტი გამოყოფილია ნიშნის შესანახად და მისი ცვლილება მოდულის ცვლილებას არ იწვევს, შესაბამისად რიცხვის მოდულის დასათვლელად საკმარისია ყველაზე მაღალ ბიტში დად...

        Intel SPMD Program Compiler, შემოკლებით ISPC, არის C-ს სტილის SPMD(ერთი პროგრამა მრავალი მონაცემი) პროგრამირების ენა, რომელიც პარალელური გამოთვლების მარტივად ჩატარების კარგ საშუალებას იძლევა. ISPC ახდენს თქვენს მიერ მიცემული კოდის გაპარალელებას პროცესორის ბირთვებში არსებულ SIMD(ერთი ინსტრუქცია მრავალი მონაცემი) გამომთვლელებზე და 3-ჯერ ან უფრო მეტჯერ ახდენს გამოთვლების აჩქარებას.         ISPC ძალიან ამარტივებს პარალელური გამოთვლების კეთების პროცესს და შესაბამისად ზრდის პროდუქტიულობას. ის არა მხოლოდ ინტერპრეტატორია კოდის არამედ შეიცავს რიგ კოდის ოპტიმიზატორებს რათა მაქსიმალურად გაზარდოს პროგრამის ეფექტურობა. თუმცა დოკუმენტაციის თანახმად დიდი ყურადღება უნდა მიექცეს მონაცემებზე წვდომას, რათა მივიღოთ ადვილად და მეტად ეფექტურად გაპარალელებადი პროგრამული კოდი. მონაცემების შეგროვება/გაბნევა( gather/scatter ) პროგრამაში ართულებს მის გაპარალელებას რაც ამცირებს ეფექტურობას. მონაცემებზე წვდომა მკვეთრად მოქმედებს წარმადობაზე, რადგან პირდაპირ არის...

Normal Distribution სურათზე ნაჩვენებია ნორმალური განაწილების გრაფიკები განსხვავებული  μ  და  σ  პარამეტრებით.         ნორმალური განაწილება არის ერთ-ერთი ყველაზე ხშირად გამოყენებადი განაწილება სტატისტიკაში. ნორმალური განაწილების სიმკვრივის ფუნქცია მოიცემა შემდეგი სახით:         ფუნქცია განსაზღვრულია მთელ ღერძზე და ორივე მიმართულებით მიისწრაფვის 0-სკენ(იხილეთ პირველი სურათი). განაწილება ხასიათდება 2 პარამეტრით  μ  და  σ .   μ  არის ფუნქციის საშუალო, რომელზეც სიმკვრივის ფუნქცია იღებს მაქსიმალურ მნიშვნელობას ხოლო  σ  არის საშუალო კვადრატული გადახრა, რომელიც განსაზღვრავს ფუნქციის გრაფიკის გაშლილობას.         ნორმალურ განაწილებას უწოდებენ სტანდარტულს თუ მისი  μ =0 და  σ=1 .

Cumulative Distribution Function         კუმულაციური განაწილების ფუნქცია F(x) აღწერს ალბათობას იმისა, რომ X შემთხვევითი სიდიდის მნიშვნელობა ნაკლებია ან ტოლი x-ზე.         კუმულაციური განაწილების ფუნქცია, როგორც სახელიდანაც ჩანს, არის დაგროვებითი. შესაბამისად ალბათობა იმისა, რომ შემთხვევითი X სიდიდე ნაკლები ან ტოლი იქნება რაიმე x მნიშვნელობაზე ტოლია ყველა იმ ალბათობების ჯამისა, რომ X ტოლი იქნება t-სი, სადაც t≤x. ალბათობა იმისა, რომ X შემთხვევითი სიდიდე ტოლი იქნება რაიმე t-სი ამის შესახებ ინფორმაციას გვაწვდის  ალბათობის სიმკვრივის ფუნქცია . როდესაც უწყვეტ ფუნქციაზე ვლაპარაკობთ ჯამის მაგივრად ვწერთ ინტეგრალს. ეს ფაქტი მათემატიკურად ასე ჩაიწერება:         სწორედ ამ თვისების გამო, რომ ფუნქცია ახდენს ალბათობების დაგროვებას ის არის დადებითი და არაკლებადი მთელს განნსაზღვრის არეზე. ალბათობის სიმკვრივის ფუნქციის შემთხვევაში შემთხვევითი სიდიდის მოხვედრის ალბათობა რაიმე (a,b] შუალედში თუ უდრის ფუნქციის წირსა და x ...

Probability Density Function         ალბათობის სიმკვრივის ფუნქცია(pdf) ასახავს ალბათობას იმისა, რომ უწყვეტი შემთხვევითი სიდიდე იღებს რაიმე მნიშვნელობას. შესაბამისად ალბათობა იმისა, რომ შემთხვევითი სიდიდე X ჩავარდება რაიმე [a,b] ინტერვალში მოიცემა ამ ინტერვალზე ფუნქციის ინტეგრალით. მათემატიკურად ასე ჩაიწერება:         ვიზუალურად რომ წარმოვიდგინოთ ეს არის შესაბამის ინტერვალში ფუნქციის წირსა და x ღერძს შორის მოქცეული ფიგურის ფართობი(იხილეთ პირველი სურათი). ფუნქციის ინტეგრალი მთელ ღერძზე არის 1-ის ტოლი. რადგან ფუნქცია ასახავს ალბათობას, შესაბამისად ის არის მთლიანად არაუარყოფითი.         ქართულ ტერმინოლოგიაში ალბათობის სიმკვრივის ფუნქციის ნაცვლად ზოგჯერ იყენებენ განაწილების სიმკვრივეს .

Rejection Sampling         შერჩევა დაწუნებით არის შერჩევის მეთოდი რომელიც ძალიან ხშირად გამოიყენება სტატისტიკური შემთხვევითი შერჩევების დროს.         განვიხილოთ დაწუნებით შერჩევის მაგალითი. ვთქვათ გვინდა მოვახდინოთ წერტილების თანაბრად განაწილებული შერჩევა ერთეულოვანრადიუსიან წრეწირში. შერჩევა დაწუნებით იღებს რაიმე შერჩევის არეს, რომელიც მოიცავს სასურველი შერჩევის არეს და ახდენს მასში შერჩევას. ამ დროს როგორც წესი აღებულ ალტერატიულ არეზე შერჩევა უფრო მარტივად ხდება. ჩვენს შემთხვევაში შეგვიძლია ავიღოთ წრეწირის შემომსაზღვრელი კვადრატი და მასში მოვახდინოთ შერჩევა. ის წერტილები რომლებიც მოხვდებიან წრეწირის შიგნით იქნებიან სასურველი შერჩევის ელემენტები, ხოლო გარეთ მოხვედრილი წერტილების დაწუნება მოხდება. თავად კვადრატში შერჩევა მარტივი პროცესია, წერტილის x, y კოორდინატებს ვიღებთ შემთხვევითად [-1,1] შუალედში.         კვადრატში წერტილების შერჩევისთვის ამ მეთოდის გამოყენება საკმაოდ გავრცელებულია. ამ შემთხვევაში დაწუნებული შერჩევე...

Structure of Arrays vs Array of Structures         ამ პოსტში ჩვენ განვიხილავთ მონაცემთა ორგანიზების 3 მექანიზმს და მათ შორის განსხვავებას: სტრუქტურების მასივს ( A rray o f S tructures). მასივების სტრუქტურას ( S tructure o f A rrays). მასივების სტრუქტურების მასივი ( A rray of S tructure of A rrays)         განვიხილოთ მონაცემების პროცესორზე გადაცემის, კეშირების და დამუშავების მექანიზმი, რომელიც დეველოპერისგან მთლიანად დამალულია. პროცესორში ინსტრუქციების და მონაცემების გადატანა ხდება პერიოდულად და იმისთვის, რომ ყოველ ახალ ინსტრუქციაზე და მონაცემზე არ მოუწიოს წინ და უკან სიარული პროცესორში აქვს შესაბამისი კეშები(ინსტრუქციების და მონაცემების), ამიტომ პროგრამის მიმდინარეობის პროცესში, როდესაც ხდება მონაცემზე მიმართვა ხდება ამ მონაცემის მცირე მიდამოს გადატანა კეშში იმ იმედით, რომ შემდეგ ინსტრუქციებზე ეს მონაცემები შეიძლება დასჭირდეს. სწორედ ამ მიზეზის გამო, მონაცემების არასწორი ორგანიზების შემთხვევაში, როდესაც საჭირო ინფორმაციები გაბნე...

Mean Shift         საშუალოთი გადაწევის ალგორითმი გვეხმარება დისკრეტულ განაწილებაში მოვძებნოთ მჭიდროდ განლაგებული ადგილები. ის ასევე გვეხმარება განაწილების მოდის პოვნაში. ის არის იტერაციული ხასიათის ევრისტიკული ალგორითმი, რომელიც პოულობს ლოკალურ ექსტრემუმს.         ვთქვათ მოცემული გვაქვს რაიმე განაწილება, სიმარტივისათვის ავიღოთ სიბრტყეზე განაწილებული წერტილები. ალგორითმი მუშაობას იწყებს რაიმე საწყის პოზიციაზე და ყოველ ბიჯზე: პოულობს r რადიუსის სიახლოვეზე არსებულ ელემენტებს მოცემულ განაწილებაში. ითვლის ამ ელემენტების წაშუალო კოორდინატს. გადავწიოთ დაკვირვების წერტილი გამოთვლილ კოორდინატზე.         ამ ბიჯებს იმეორებს მანამ, სანამ არ იპოვის ლოკალურ ექსტრემუმს(მჭიდროდ განაწილებულ რეგიონს) და გაჩერდება. ამ დროს ალგორითმის მეორე პუნქტი იქნება უშედეგო და დაემთხვევა წინა ბიჯზე გამოთვლილ კოორდინატს. მეტი სიცხადისთვის იხილეთ ვიდეო.         ამ ვიდეოში ნაჩვენებია შემთხვევა როდესაც ერთი გამოკვეთილად მჭიდრ...

K-means clustering         ვთქვათ მოცემული გვაქვს n ცალი დაკვირვების წერტილი (x 1 , x 2 , x 3 , ... , x n ), რომელთაგან თითოეული წარმოადგენს d განზომიალებიან ვექტორს. ამოცანა მდგომარეობს შემდეგში, რომ ჩვენ უნდა დავყოთ n ცალი დაკვირვების წერტილი K კლასტერად (k  ≤  n) S = {S 1 , S 2 , S 3 , ..., S k } ისე რომ ნებისმიერი წერილი მოხვდეს კლასტერში და თითოეული კლასტერისათვის მოვახდინოთ კვადრატების ჯამის მინიმიზაცია:         სადაც  μ i  არის i-ური კლასტერის წერტილების საშუალო. ეს პრობლემა შედის NP-რთული ამოცანების ჯგუფში . K-საშუალოს კლასტერიზაციის მეთოდი არის ევრისტიკული მეთოდი რომელიც საკმაოდ სწრაფად წყვეტს ამ ამოცანას და პოულობს ლოკალურ მინიმუმს. თუმცა პრაქტიკულ ამოცანებში ეს მინიმუმი ხშირად ემთხვევა გლობალურს.         რაც შეეხება თავად K-საშუალოს კლასტერიზაციის ალგორითმს, ის მთლიანად დაფუძნებულია Lloyd-ის ალგორითმზე . თავდაპირველად ხდება მოცემულ n წერტილზე ვორონოის დიაგრამის აგება შემთხვევითად ა...

Lloyd's algorithm         ლოიდის მეთოდს ასევე უწოდებენ ლოიდის განტვირთვას(Lloyd's Relaxation) გვეხმარება, რომ მოვახდინოთ ტრანსფორმაცია n განზომილებიან სივრცეში მოცემული წერტილების მიმდევრობისა ისე რომ ისინი იყვნენ  სივრცეში   თანაბრად  განაწილებული . ალგორითმის მუშაობის პრინციპი ძალიან მარტივია: ვთქვათ მოცემული გვაქვს ვორონოის დიაგრამა n გენერატორით. ვორონოის ყველა რეგიონისთვის უნდა ვიპოვოთ "ცენტრი ს " პოზიცია ( უმეტეს შემთხვევაში ხდება გეომეტრიული სიმძიმის ცენტრის აღება ) და ამ რეგიონის შესაბამისი გენერატორი გადავიტანოთ მიღებულ პოზიციაზე. განვაახლოთ ვორონოიდ დიაგრამა.   ეს პროცესი გავიმეოროთ იტერაციულად რამდენჯერმე. ლოიდის განტვირთვის ყოველი იტერაცია მოახდებს წერტილების სივრცეში განლაგების განაწილების ცვლილებას და იტერაციების ზრდასთან ერტად განაწილება მიუახლოვდება თანაბარს. მეტი სიცხადისთვის შეგვიძლია ვნახოთ ვიდეო:         ლოიდის მეთოდს ხშირად იყენებენ თანაბარი მეშირების დროს.

Voronoi Diagram ვორონოის დიაგრამა ( Voronoi Diagram ) არის სივრცის დაყოფის ერთერთი გზა. თუ მოცემული გვაქვს m ელემენტიანი წერტილების(პირობითად ვუწოდოთ მათ გენერატორები) მიმდევრობა n განზომილებიან სივრცეში მაშინ შეგვიძლია სივრცე დავყოთ ისეთ m რეგიონებად, სადაც ყოველ გენერატორს შეესაბამება ერთ რეგიონი და სრულდება პირობა: ყოველი რეგიონის ნებისმიერი წერტილისათვის მისი შესაბამისი გენერატორი არის უახლოესი მოცემულ m გენერატორს შორის. წერტილები რომლებიც თანაბრად არიან დაშორებული 2 გენერატორიდან შეადგენენ სეგმენტებს(segments). წერტილები რომლებიც თანაბრად არიან დაშორებული 3 (ან მეტი) წერტილიდან ეწოდებათ ვორონოის კვანძები(nodes). სახელი ვორონოი მოდის ცნობილი უკრაინელი მათემატიკოსის გიორგი ვორონოის გვარიდან. ვორონოის დიაგრამა არის პრაქტიკულად იგივე რაც დელონის ტრიანგულაცია . სურათზე ნაჩვენებია ვორონოის დიაგრამა ორგანზომილებიან სივრცეში. შავი ფერის წერტილებით აღნიშნულია გენერატორები. ვორონოის რეგიონები გაფერადებულია სხვადასხვა ფერით. ვორონოის დიაგრემებს ძალიან ფართო გამოყენება აქვს კომპიუტერ...