ETD Collection

Permanent URI for this collectionhttps://wiredspace.wits.ac.za/handle/10539/104


Please note: Digitised content is made available at the best possible quality range, taking into consideration file size and the condition of the original item. These restrictions may sometimes affect the quality of the final published item. For queries regarding content of ETD collection please contact IR specialists by email : IR specialists or Tel : 011 717 4652 / 1954

Follow the link below for important information about Electronic Theses and Dissertations (ETD)

Library Guide about ETD

Browse

Search Results

Now showing 1 - 1 of 1
  • Item
    Parallel algorithms for querying spatial properties in the protein data bank
    (2019) Selvan, Joshua
    Searching large protein databases for proteins with certain structural properties is expensive. This research explored the use of GPGPUs (General Purpose Graphical Processing Units) in speeding up such structural queries. Brute force and kd-tree spatial data structure algorithms were compared and benchmarked against non-GPU parallel algorithms to assess the e ectiveness of using GPGPUs. This was done with the aim of increasing the speed at which queries against large protein databases can be completed to help mitigate the e ect of increasing data set sizes of current protein databases [56]. A set of parallel variations of range search algorithms were developed and imple- mented in the GPU programming language CUDA and their performances times in completing batch range search jobs were compared against other parallel approach types such as multi-threading and message passing to see if the GPU approaches completed notably faster or slower than more traditional parallelised approaches. The results showed GPGPUs can construct kd-trees far faster than other parallelised implementations can achieve and that in most scenarios (excluding speci c cases such as very low or zero result searches) the GPGPU approaches either matched or performed far better than the other parallelised approaches. While comparing di erent GPU algorithms, the complex GPU based kd-tree algo- rithm performed similarly to a simple GPU brute force range search. This high- lighted the bene ts of writing code which made the most of the GPU's parallel architecture as opposed to modifying e cient (recursive) algorithms to adequately t into those same GPU architectures. This implied that even though spatial data structures are e ective ways of dealing with protein data, there are better returns on e ort in writing code speci cally for the GPU's inherently parallel architecture for initiatives which require algorithms to be developed from scratch.