Enhancing the MMD algorithm in multi-core environments

Simple item page
dc.contributor.advisorKent, Kenneth
dc.contributor.advisorHerpers, Rainer
dc.contributor.authorSchlösser, Michael
dc.date.accessioned2023-03-01T16:35:52Z
dc.date.available2023-03-01T16:35:52Z
dc.date.issued2011
dc.date.updated2016-12-13T00:00:00Z
dc.description.abstractThe work done in this thesis enhances the MMD algorithm in multi-core environments. The MMD algorithm, a transformation based algorithm for reversible logic synthesis, is based on the works introduced by Maslov, Miller and Dueck and their original, sequential implementation. It synthesises a formal function specification, provided by a truth table, into a reversible network and is able to perform several optimization steps after the synthesis. This work concentrates on one of these optimization steps, the template matching. This approach is used to reduce the size of the reversible circuit by replacing a number of gates that match a template which implements the same function and uses less gates. Smaller circuits have several benefits since they need less area and are not as costly. The template matching approach introduced in the original works is computationally expensive since it tries to match a library of templates against the given circuit. For each template at each position in the circuit, a number of different combinations have to be calculated during runtime resulting in high execution times, especially for large circuits. In order to make the template matching approach more efficient and usable, it has been reimplemented in order to take advantage of modern multi-core architectures such as the Cell Broadband Engine or a Graphics Processing Unit. For this work, two algorithmically different approaches that try to consider each multi-core architecture’s strengths, have been analyzed and improved. For the analysis these approaches have been cross-implemented on the two target hardware architectures and compared to the original parallel versions. Important metrics for this analysis are the execution time of the algorithm and the result of the minimization with the template matching approach. It could be shown that the algorithmically different approaches produce the same minimization results, independent of the used hardware architecture. However, both cross-implementations also show a significantly higher execution time which makes them practically irrelevant. The results of the first analysis and comparison lead to the decision to enhance only the original parallel approaches. Using the same metrics for successful enhancements as mentioned above, it could be shown that improving the algorithmic concepts and exploiting the capabilities of the hardware lead to better results for the execution time and the minimization results compared to their original implementations.
dc.description.copyright© Michael Schlösser, 2011
dc.description.noteElectronic Only. (UNB thesis number) Thesis 8689. (OCoLC) 960950379
dc.description.noteM.C.S., University of New Brunswick, Faculty of Computer Science, 2011.
dc.formattext/xml
dc.format.extentx, 139 pages
dc.format.mediumelectronic
dc.identifier.oclc(OCoLC) 960950379
dc.identifier.otherThesis 8689
dc.identifier.urihttps://unbscholar.lib.unb.ca/handle/1882/14176
dc.language.isoen_CA
dc.publisherUniversity of New Brunswick
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.subject.disciplineComputer Science
dc.subject.lcshComputer algorithms
dc.subject.lcshOpenCL (Computer program language)
dc.subject.lcshMultiprocessors
dc.subject.lcshLogic circuits
dc.subject.lcshReversible computing
dc.titleEnhancing the MMD algorithm in multi-core environments
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.fullnameMaster of Computer Science
thesis.degree.grantorUniversity of New Brunswick
thesis.degree.levelmasters
thesis.degree.nameM.C.S.

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
item.pdf
Size:
1.84 MB
Format:
Adobe Portable Document Format
Download

Collections

Open Theses & Dissertations