University of Macau / Faculty of Science and Technology / Department of Computer and Information Science

University of Macau / Faculty of Science and Technology / Department of Computer and Information Science

University of Macau / Faculty of Science and Technology / Department of Computer and Information Science

University of Macau / Faculty of Science and Technology / Department of Computer and Information Science

Indian Institute of Science / A large number of mathematical models in engineering and physical sciences employ Partial Differential Equations (PDEs). The sheer number of operations required in numerically integrating PDEs in these applications has motivated the search for faster methods of computing. The conventional uniprocessor computers are often unable to fulfill the performance requirements for these computation intensive problems. In this dissertation, a cost-effective message-based multiprocessor system which we call the Broadcast Cube System (BCS) has been proposed for solving important computation intensive problems such as, systems of linear algebraic equations and PDEs. A simulator for performance evaluation of parallel algorithms to be executed on the BCS has been implemented. A strategy (task assignment . algorithm) for assigning program tasks with precedence and communication constraints to the Processing Elements (PEs) in the BCS has been developed and its effectiveness demonstrated. This task assignment algorithm has been shown to produce optimal assignments for PDE problems. Optimal partitioning of the problems, solving systems of linear algebraic equations and PDEs, into tasks and their assignment to the PEs in the BCS have been given. Efficient parallel algorithms for solving these problems on the BCS have been designed. The performance of the parallel algorithms has been evaluated by both analytical and simulation methods. The results indicate that the BCS is highly effective in solving systems of linear algebraic equations and PDEs. The performance of these algorithms on the BCS has also been compared with that of their implementations on popular hypercube machines. The results show that the performance of the BCS is better than that of the hypercubes for linear algebraic equations and compares very well for PDEs, with a modest number of PEs despite the constant PE connectivity of three in the BCS. Finally, the effectiveness of the BCS in solving non-linear PDEs occurring in two important practical problems, (i) heat transfer and fluid flow simulation and (ii) global weather modeling, has been demonstrated.

Internet has changed our lives. It has made the true distributed computing paradigm a reality. It has opened up a lot of opportunities both in the research domain and in business domain. One can now think of developing software and make it available to the large community of users. Hyper Text Transfer Protocol (HTTP), which was originally developed for the purpose of requesting/transferring content (text, images, etc.), is now a standard for remotely invoking services and getting back results. The wireless technologies have also matured. 802.11 is the existing standard for wireless communication in a LAN environment. Today, even the small computers like the Personal Digital Assistants (PDA) is wireless enabled. This makes access to information and computing significantly much more convenient. Hotspot! server has been designed to provide connectivity and services in public places (called hotspots). It acts as a wireless Network Access Server (NAS) to users who want to obtain connectivity and services at public places. We believe that the primary applications that have importance and relevance in public places are Internet Access, and specific context-based or location specific services. These services are deployed by Internet Service Providers. Secure access is one of the primary concerns in public networks. We designed, developed and tested a framework for secure access to HTTP-based services through the Hotspot! server. Internet Access is a special case of a HTTP-based Proxy service.

Precise specification of the architecture and design of software is a good practice. Such specifications contain a lot of information about the software that can potentially be exploited by tools, to reduce redundancy in software writing by automating routine tasks, as well as giving valuable feedback on the software. We first broadly classify such tools based on their application, and look at some of the issues involved in writing them. Most of these tools are built using conventional programming languages that do not provide primitives that are routinely required by such tools. We identify some patterns that are seen while writing such tools and abstract them out into a language specially designed for the purpose. Our effort is a language called LEADS, where we attempt to make writing such tools a lot easier, modular, organized and portable. LEADS is based on the Pattern-Action approach, where one specifies the pattern of information of interest and the actions to be taken when it is found. The patterns are specified using a custom declarative language that is enriched with special primitives for routinely occurring constructs. LEADS also decouples itself from the specification environments and formats thereby ensuring wide applicability. This enables LEADS scripts to be ported across design environments with minimal effort.

We have implemented Occam, a parallel programming language, on a uniprocessor machine (MC-68020 based HORIZON I11 running on UNIX system V.2) with simulated concurrency. Occam is a descendant of CSP with a few convenient modifications like channels used for communication and procedures. Two additions to the original language, i.e., output guards and recursion have been proposed. Front end of the compiler was developed using LEX and YACC. An innovative code generator, generator based on tree pattern matching has been used to generate the back end of the compiler, which generates efficient MC-68020 assembly code. A kernel for process administration is the runtime support provided. It has been developed entirely in ' C ' and made available as a library. This is linked with the assembly module to generate the executable version of the input Occam program. We have also interfaced our Occam compiler with Unix system V.2 source level debugger 'Sdb' so as to provide debugging support for Occam programmers. Issues involved in parallel debugging have been investigated and those demanding minimum effort have been incorporated in Occam debugger by modifying the runtime support of the uniprocessor implementation. Modifications to the uniprocessor implementation so as to make it run on a shared memory multiprocessor machine(HCL MAGNUM-P with four MC-68030 processors) are also discussed. The support provided by MAGNUM-P at the architecture and operating system levels is explained in detail. Our Occam compiler for the multiprocessor generates code, but the generated code has not been tested since the machine is not yet ready.

With the advent of Distributed Memory Machines (DMMs) numerous work have been undertaken to ease the work of a programmer these systems. Data parallel languages like Fortran D, Vienna Fortran, High Performance Fortran and C+ allow the user to specify data distribution across processor with some directives, and the compiler for these language use the directives to compile the programme in to an SPMD code. There are number of old program which are still in use and rewriting them in to new data parallel languages is a costly effort. Most of the work on these parallelizing compilers concentrate on efficient data communication between the processors.With the advancement in technology, data communication time is also decreasing.This allows bigger programs to execute in the same time span.The resources of a DMM being finite puts a limit on the size of the problem that can be run. Improving the memory usage for a problem will hence allow us run bigger size problems. Further, as communication speed increases, the overhead caused by house-keeping computations like global index to local index transformation, and owner processor computation will degrade the performance of the resultant code. Hence a uniform and efficient method for these computations also becomes a necessity. We have implemented parallelizing parts of a compiler using the SUIF compiler system, which accepts programs written in Fortran77 with directives to the compiler as comments. The output of the compiler is an SPMD C program, with embedded PVM calls for message communication between the processors. We have also proposed algorithms to improve data communications,and minimizing memory usage in the output code. A uniform method for performing owner processor computations and global-to-local transformations has also been implemented.

Code optimization or code transformation is a complex function of a compiler involving analyses and modifications with the entire program as its scope. In spite of its complexity, hardly any tools exist to support this function of the compiler. This thesis presents the development of a code transformation system, specifically for scalar transformations, which can be used either as a tool to assist the generation of code transformers or as an environment for experimentation with code transformations. The development of the code transformation system involves the formal specification of code transformations using dependence relations. We have written formal specifications for the whole class of traditional scalar transformations, including induction variable elimination - a complex transformation - for which no formal specifications are available in the literature. All transformations considered in this thesis are global. Most of the specifications given here, for which specifications are already available in the literature, are improved versions, in terms of conservativeness.The study of algorithms for code transformations, in the context of their formal specification, lead us to the development of a new algorithm for partial redundancy elimination. The basic idea behind the algorithm is the new concepts of safe partial availability and safe partial anticipability. Our algorithm is computationally and lifetime optimal. It works on flow graphs whose nodes are basic blocks, which makes it practical.In comparison with existing algorithms the new algorithm also requires four unidirectional analyses, but saves some preprocessing time. The main advantage of the algorithm is its conceptual simplicity. The code transformation system provides an environment in which one can specify a transformation using dependence relations (in the specification language we have designed), generate code for a transformer from its specification,and experiment with the generated transformers on real-world programs. The system takes a program to be transformed, in C or FORTRAN, as input,translates it into intermediate code, interacts with the user to decide the transformation to be performed, computes the necessary dependence relations using the dependence analyzer, applies the specified transformer on the intermediate code, and converts the transformed intermediate code back to high-level. The system is unique of its kind,providing a complete environment for the generation of code transformers, and allowing experimentations with them using real-world programs.