Browsing by Author "Siau Cheng KHOO"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Affine-Based Size-Change Termination
    (2003-09-01T00:00:00Z) Anderson Hugh; Siau Cheng KHOO
    The size-change principle devised by Lee, Jones and Ben-Amram, provides an effective method of determining program termination for recursive functions over well-founded types. Termination analysis using the principle involves the classication of functions either into size-change terminating ones, or ones which are not size-change terminating. Size-change graphs are constructed to represent the functions, and decreasing parameter sizes in those graphs that are idempotent are identifed. In this paper, we propose a translation of the sizechange graphs to affine-based graphs, in which affine relations among parameters are expressed by Presburger formulae. We show the correctness of our translation by defining the size-change graph composition in terms of affine relation manipulation, and identifying the idempotent size-change graphs with transitive closures in affine relations. We then propose an affine-based termination analysis, in which more refined termination size-change information is admissible by affine relations. Specifically, our affine-related analysis improves the effectiveness of the termination analysis by capturing constant changes in parameter sizes, affine relationships of the sizes of the source parameters, and contextual information pertaining to function calls. We state and reason about the corresponding soundness and termination of this affine-related analysis. Our approach widens the set of size-change terminating functions.
  • No Thumbnail Available
    Item
    A Type-Based Approach to Parallelization
    (2003-10-01T00:00:00Z) Dana N. XU; Siau Cheng KHOO; Wei Ngan CHIN; Zhenjiang HU
    Parallel functional programming plays an important role in parallel programming [16]. Type system has signi.cant impact on program analysis [23]. In this paper, we show how to automatically and correctly synthesize parallel programs from sequential functional program based on the concept of a type system. Our type system captures the parallelizability of a program, in a modular fashion, by exploring the ring structures of the programs operators. It handles programs de.ned by self-recursive functions with accumulating parameters, as well as a limited form of non-linear mutual-recursive functions. In contrast to the Damas-Milner type system (the typical type system) that is constructed from the evaluation rules of the underlying language, our type system is constructed from a set of meta-rules that are used to transform sequential programs into a special normal form suitable for parallelization. The idea of this paper has been implemented and used to generate parallel code of a form, called mutumorphism, a general parallel computation model. Transforming into such a form is an important step towards constructing e.cient data parallel programs.