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.

School

School of Sciences and Engineering

Department

Computer Science & Engineering Department

Degree Name

MS in Computer Science

Date of Award

6-1-2002

Online Submission Date

2-13-2013

First Advisor

Samed, Ahmed

Committee Member 1

Sameh, Ahmed

Committee Member 2

Salem, Abdel Badie

Document Type

Thesis

Extent

183 p.

Rights

The American University in Cairo grants authors of theses and dissertations a maximum embargo period of two years from the date of submission, upon request. After the embargo elapses, these documents are made available publicly. If you are the author of this thesis or dissertation, and would like to request an exceptional extension of the embargo period, please write to thesisadmin@aucegypt.edu

IRB

Not necessary for this item

Download

Share

COinS