Author

Manal Helal

Abstract

This thesis implements a model for the shape and dimension invariant programming based on the notation of the Mathematics of Arrays (MOA) algebra. It focuses on dimension and shape invariance implementation, and their effect in parallel computing. A new design for the MOA notation is implemented that eliminates the need for another PSI-compiler, or a language extension to functional programming languages. The MOA notation is designed as a library of Application Programming Interfaces (APIs), contains object oriented classes implemented in C++. The library executes array operations correctly, and is expected to enhance the performance invariant of dimension and shape. To implement these APIs, the mathematical equations of the original notation were analyzed and sometimes simplified to become more comprehensible to implement from the programming point of view, and some more operations were added. The APIs reduce the erroneous loops starts, strides, and stops used by programmers in the traditional handling of multi-dimension arrays. The library defines the dimension and shape of the arrays at runtime; and gives the source code of the problem in hand better chances to be automatically parallelized. The MOA library testing tool developed and implemented in this thesis, can be used by mathematicians and computer arithmetic researchers to translate high level arithmetic functions in applications like image processing, video -111 processing, fluid dynamic, ... etc. to the MOA notation, utilizing its benefits. An image-processing tool is implemented using this new MOA library, proving the correctness of the design on 2D-array application, where image operations are expressed concisely in the source code and easily manipulated on the conceptual leveL Image processing transfonnations, filtering and detections are implemented. Video processing operations like transformations on the AVI Frames after decomposing them, and motion detection scheme are implemented using the MOA library, to prove the correctness of the library on a 3D-array application. Also, the parailelisation factors inherent in the MOA library design are discussed in terms of shape polymorphism, MOA parallel architecture, data redistribution, and Tiling algorithms, in relation to the MOA notation. Furthermore, pipelining with MOA has been investigated. In addition to the above experiments, a hardware implementation of the MOA APIs was implemented using VHDL on Renoir as a package, and simulated using ModelSim. Perfonuance analysis is conducted in tenus of general benefits of programming invariant of shape and dimension as designed in this thesis, which is open to further analysis based on the application domain.

Department

Computer Science & Engineering Department

Degree Name

MS in Computer Science

Date of Award

6-1-2002

Online Submission Date

February 2013

First Advisor

Samed, Ahmed

Committee Member 1

Sameh, Ahmed

Committee Member 2

Salem, Abdel Badie

Document Type

Thesis

Extent

183 p.

Rights

The author retains all rights with regard to copyright. The author certifies that written permission from the owner(s) of third-party copyrighted matter included in the thesis, dissertation, paper, or record of study has been obtained. The author further certifies that IRB approval has been obtained for this thesis, or that IRB approval is not necessary for this thesis. Insofar as this thesis, dissertation, paper, or record of study is an educational record as defined in the Family Educational Rights and Privacy Act (FERPA) (20 USC 1232g), the author has granted consent to disclosure of it to anyone who requests a copy. The author has granted the American University in Cairo or its agents a non-exclusive license to archive this thesis, dissertation, paper, or record of study, and to make it accessible, in whole or in part, in all forms of media, now or hereafter known.

IRB

Not necessary for this item

Share

COinS