Mandelbrot kao karta Julijinih atraktora kroz paralelno programiranje

undergraduate thesis

• Title (english): Mandelbrot as map of Julia's attractors with parallel programming
• Author: Barbara Drašković
• Mentor: Mervan Pašić (mentor)
• Committee member: Mervan Pašić (predsjednik povjerenstva)
• Committee member: Lana Horvat Dmitrović (član povjerenstva)
• Committee member: Anamari Nakić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-07-10, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Fraktali su samoslični objekti ne cjelobrojne dimenzije. Algebarski fraktali dobiju se iteracijom kroz odgovarajuću formulu u kojoj je izlaz iz formule ulaz u novu iteraciju. Brojevi za koje se ispituje pripadnost fraktalu mogu konvergirati ili divergirati. Ako konvergiraju unutar su skupa algebarskog fraktala. Ako divergiraju izvan su skupa. Granica između točaka koje divergiraju i konvergiraju ima fraktalnu dimenziju. Ako je početna konstanta za Julijin skup dio Mandelbrotovog skupa, brojevi kojima točke Julijinog skupa konvergiraju mogu se izračunati. U radu se za sve Julijine skupove provjerava konvergiraju li k tim točkama i na taj način se iscrtava Mandelbrotov fraktal. U radu je i eksperimentalno pokazano da svi Julijni skupovi čija početna konstanta pripada Mandelbrotovom skupu imaju jedan atraktor (nađen na pozitivnom dijelu apscise) čija je apsolutna vrijednost manja od jedan. Zbog enormne količine izračuna problem se rješava kroz paralelno programiranje uz OpenCL. Grafička kartica koristi se kao akcelerator jer ima više izvršnih jedinica koje rade sa SIMD vektorskim jedinicama. Na svakoj izvršnoj jedinici u jednom ciklusu se izvršava jedna radna skupina koja dijeli lokanu memoriju. Svakoj radnoj jedinici grafička kartica pristupa preko globalnog ID-a. Nad podacima se izvršava isti niz operacija, odnosno kernel. Kernel stvaramo nakon što smo uspostavili komunikaciju s platformom, pa s uređajem, stvorili kontekst, stvorili red naredbi i povezali ga s uređajem i kontekstom, stvorili CL program i povezali ga s uređajem i kontekstom te ga kompajlirali. Kernel pokrećemo povezujući ga s redom uređaja na kojem ga želimo pokrenuti. Po završetku izvođenja rezultat se može upisati u izlazni argument koji je predan pokazivač prilikom poziva kernelu.
Ovim pristupom smo pospješili brzinu analize ovog kompleksnog problema.

Abstract (english)

Fractals are self-similar objects with fractal dimensions. Algebraic fractals are generated with large number of iterations of specific formula where exit expression becomes a new entrance to equation. The numbers that we are trying to qualify in Escape or Prisoner set can diverge or converge in a big number of iterations. If they converge they belong to Prisoner set and if they diverge they belong to Escape set. Limit of those two sets has fractal dimension. If complex constant c for Julia belongs to Mandelbrot set, attractors for Julia can be calculated. In this paper, we calculate do those attractors appeal Julia sets. If they do, they belong to Mandelbrot. That is how we design our Mandelbrot set. We also demonstrate that Julia set for which we know how to calculate attractors has one attractor (found on x-axis) of absolute value smaller than one. Because of the enormous size of the data problem is solved through parallel programing with OpenCL. GPU is used as an accelerator because it has many compute units and each one of them consists of multiple SIMD vector unit. On every compute unit in one cycle one work group completes one operation. Work group shares local memory. GPU has control on every work item through its global ID. We run same operations (kernel) on all data within a set. We create kernel after we have established communication with platform, with device, after we have created context and linked it with device, after we have created command queue and linked it with context and with the device, created CL program, linked it with the device, context and compiled it. Kernel starts execution when it’s linked with the command queue. After all the data is done we can write the exit in the argument that we set as a pointer (and specify with write flag) when we started kernel execution. With this approach, we have accelerated the process of solving this complex assignment.

• Keywords: Mandelbrot; Julia; fraktali; atraktori; OpenCL; GPU; paralelno programiranje
• Keywords (english): Mandelbrot; Julia; fractlas; attractors; OpenCL; GPU; parallel programming
• Language: croatian
• URN:NBN: urn:nbn:hr:168:481581
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 20:00:40