Chau, Wai Shing. / Thesis submitted in: October 2007. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 64-66). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Ad hoc network --- p.1 / Chapter 1.2 --- Outline of the thesis --- p.3 / Chapter 2 --- Background Study --- p.4 / Chapter 2.1 --- Multiple Access Control (MAC) --- p.4 / Chapter 2.1.1 --- Time Division Multiple Access (TDMA) --- p.5 / Chapter 2.1.2 --- Spatial TDMA (STDMA) --- p.5 / Chapter 2.2 --- Interference Models --- p.6 / Chapter 2.2.1 --- Primary and Secondary Interferences --- p.6 / Chapter 2.2.2 --- Interference-based Model --- p.7 / Chapter 2.2.3 --- Graph-based Model --- p.7 / Chapter 2.3 --- Scheduling in Graph-based Model --- p.8 / Chapter 2.3.1 --- Conflict Graph --- p.9 / Chapter 3 --- Scheduling Algorithms in Ring Networks --- p.11 / Chapter 3.1 --- Problem Formulation --- p.12 / Chapter 3.2 --- Regular Sequences --- p.14 / Chapter 3.3 --- Scheduling in Ring Networks with Even-number of Edges --- p.22 / Chapter 3.4 --- Scheduling in Ring Networks with an Odd-number of Edges --- p.26 / Chapter 3.4.1 --- Scheduling by Reducing a Ring Network with an Odd-number of Edges into a Ring- Network with an Even-number of Edges --- p.28 / Chapter 3.4.2 --- Scheduling by Shifting the Regular Sequences --- p.32 / Chapter 3.5 --- Discussion --- p.42 / Chapter 3.6 --- Conclusion --- p.42 / Chapter 4 --- Distributed Scheduling Algorithm for Ad Hoc Network --- p.43 / Chapter 4.1 --- Problem Formulation --- p.44 / Chapter 4.2 --- Distributed Scheduling Heuristic Algorithm --- p.44 / Chapter 4.2.1 --- Weight functions --- p.44 / Chapter 4.2.2 --- Main Algorithm --- p.46 / Chapter 4.3 --- Centralized algorithm on a chain network --- p.49 / Chapter 4.4 --- Performance of the Algorithm on Chain Network --- p.50 / Chapter 4.4.1 --- Comparison 1 --- p.51 / Chapter 4.4.2 --- Comparsion 2 --- p.52 / Chapter 4.4.3 --- Comparsion 3 --- p.53 / Chapter 4.5 --- Performance of the Algorithm on Random Conflict graph --- p.55 / Chapter 4.6 --- Discussion --- p.57 / Chapter 4.7 --- Special Graphs --- p.58 / Chapter 4.8 --- Conclusion --- p.61 / Chapter 5 --- Conclusion --- p.62 / Bibliography --- p.64

Whole array operations and array section operations are important features of many data-parallel languages. Efficient implementation of these operations on distributed- memory multicomputers is critical to the scalability and high-performance of data-parallel programs. This thesis presents an approach for analyzing communication patterns induced by array operations and for using run-time information to schedule the message flow. The distributed, dynamic scheduling algorithms guarantee link-contention-free data transfer and utilize network resources almost optimally. They incur little overhead, which is important in order not to reduce the speedup gained by the parallel execution. The algorithms can be used by compilers for the generation of efficient code for array operations. Implemented in a runtime library, they can derive a schedule depending on parameters passed by the parallel application. Simulation results demonstrate the algorithms' superiority to the asynchronous transfer mode that is commonly used for this type of communication.

Traditionally, on-chip network communication was achieved with shared medium networks where devices shared the transmission medium with only one device driving the network at a time. To avoid performance losses, it required a fast bus arbitration logic. However, a single shared bus has serious limitations with the heterogeneous and multi-core communication requirements of today's chip designs. Point-to-point or direct networks solved some of the scalability issues, but the use of routers and of rather complex algorithms to connect nodes during each cycle caused new bottlenecks. As technology scales, the on-chip physical interconnect presents an increasingly limiting factor for performance and energy consumption. Network-on-chip, an emerging interconnect paradigm, provide solutions to these interconnect and communication challenges. Motivated by future bottom-up self-assembled fabrication techniques, which are believed to produce largely unstructured interconnect fabrics in a very inexpensive way, the goal of this thesis is to explore the design trade-offs of such irregular, heterogeneous, and unreliable networks. The important measures we care about for our complex on-chip network models are the information transfer, congestion avoidance, throughput, and latency. We use two control parameters and a network model inspired by Watts and Strogatz's small-world network model to generate a large class of different networks. We then evaluate their cost and performance and introduce a function which allows us to systematically explore the trade-offs between cost and performance depending on the designer's requirement. We further evaluate these networks under different traffic conditions and introduce an adaptive and topology-agnostic ant routing algorithm that does not require any global control and avoids network congestion.

The diversity of application programs and parallel architectures makes the mapping problem complicated and hard to evaluate. The quality of mapping is machine and application dependent and varies due to inaccurate values of application and architecture characteristics. A system for developing, applying and evaluating mappings must have four characteristics: (1) Simplicity: A mapping procedure can be evaluated by separately evaluating its submapping, so the complicated problem can be simplified. (2) Generality: A wide range of application programs and architectures can be easily represented and all mapping algorithms can be easily implemented. (3) Multifunctionality: all the mapping steps, application programs, target architectures, and related cost functions can vary and are easy to evaluate. (4) Ability for the sensitivity analysis: The sensitivity of mapping quality to the inaccuracy of cost functions and characteristics of applications and architectures can be easily tested. ParPlum, which is presented in this thesis, is aimed at creating and evaluating mappings on different parallel architectures with different application programs. Sensitivity analysis is another major focus. The design philosophy of ParPlum is to narrow down the multidimensional optimization problem into sub-problems with one or fewer dimensions. Mapping, for example, can be divided into three submappings, partitioning, allocating, and scheduling. This leads to the implementation of the ParPlum system, the use of data flow style, the distribution of ParPlum libraries, and the development of the ParPlum pipeline.

The application of Moore's Law would not be feasible by using the computing systems fabrication principles that are prevalent today. Fundamental changes in the field of computing are needed to keep Moore's Law operational. Different quantum technologies are available to take the advancement of computing into the future. Logic in quantum technology uses gates that are very different from those used in contemporary technology. Limiting itself to reversible operations, this thesis presents different methods to realize these logic gates. Two methods using Generalized Ternary Gates and Muthukrishnan Stroud Gates are presented for synthesis of ternary logic gates. Realizations of well-known quantum gates like the Feynman gate, Toffoli Gate, 2-qudit and 3-qudit SW AP gates are shown. In addition a new gate, the Inverse SW AP gate, is proposed and its realization is also presented.

In recent years, there is an increased interest in the design of logic circuits which use EXOR gates. Particular interest is in the minimization of arbitrary Exclusive Sums Of Products (ESOPs). Functions realized by such circuits can have fewer gates, fewer connections, and take up less area in VLSI and especially, FPGA realizations. They are also easily testable. So far, the ESOPs are not as popular as their Sum of Products (SOP) counterparts. One of the main reasons it that the problem of the minimization of ESOP circuits was traditionally an extremely difficult one. Since exact solutions can be practically found only for functions with not more than 5 variables the interest is in approximate solutions. Two approaches to generate s~b optimal solutions can be found in the literature. One approach is to minimize sub-families of ESOPs. Another approach is to minimize ESOPs using heuristic algorithms. The method we introduced in this thesis belongs to the second approach, which normally generates better results than the first approach. In the second approach, two general methods are used. One method is to minimize the coefficients of Reed-Muller forms. Another method is to perform a set of cube operations iteratively on a given ESOP. So far, this method has achieved better results than other methods. In this method (we call it cube operation approach), the quality of the results depends on the quality of the cube operations. Different cube operations have been invented in the past a few years. All these cube operations can be applied only when some conditions are satisfied. This is due to the limitations of the operations. These limitations reduce the opportunity to get a high quality solution and reduce the efficiency of the algorithm as well. The efforts of removing these limitations led to the invention of our new cube operation, exorlink, which is introduced in this thesis. Exorlink can be applied on any two cubes in the array without condition. All the existing cube operations in this approach are included in it. So this is the most general operation in this approach. Another key issue in the cube operation approach is the efficiency of the algorithm. Existing algorithms perform all possible cube operations, and give litter guide to select the operations. Our new algorithm selectively performs some of the possible operations. Experimental results show that this algorithm is more efficient than existing ones. New algorithms to minimize multiple output functions and especially incompletely specified ESOPs are also presented. The algorithms are included in the program EXORCISM-MV -2, which is a new version of EXORCISM-MY. EXORCISM-MV -2 was tested on many benchmark functions and compared to the results from literature. The program in most cases gives the same or better solutions on binary and 4-valued completely specified functions. More importantly, it is able to efficiently minimize arbitrary-valued and incompletely specified functions, while the programs from literature are either for completely specified functions, or for binary variables. Additionally, as in Espresso, the number of variables in our program is unlimited and the only constraint is the number of input cubes that are read, so very large functions can be minimized. Based on our new cube operation and new algorithms, in the thesis, we present a solution to a problem that has not yet been practically solved in the literature: efficient minimization of arbitrary ESOP expressions for multiple-output multiple-valued input incompletely specified functions.

The estimation of sinewave parameters has many practical applications in test and data processing systems. Measuring the effective bits of an analog-to-digital converter and linear circuit identification are some typical examples. If a sinew ave's frequency is known, there is an established linear method to estimate the other parameters. But when none of the parameters are known (which is usually the case in practical situations), the estimation problem becomes more difficult. Traditional approaches to this task applied an iterative, sinewave curve-fit algorithm. Two problems with this technique are that convergence is often slow and not always guaranteed and the results of different trials may be inconsistent due to trapping at a local minimum. Recently, a non-iterative algorithm has been developed which computes all four sine wave parameters directly. The algorithm combines a nonlinear technique and windowing to compute the estimates. Although this method is faster and more consistent than the curve-fit approach, one disadvantage is that the accuracy of some estimates tends to deteriorate rapidly if the sinusoid is corrupted by a high level of noise distortion. This study presents an improved algorithm to extract the four parameters of an unknown sinusoid from a sampled data record even though the samples may be distorted by a high level of noise. Given this record, the proposed method first computes the FFT (Fast Fourier Transform) of the data. Analysis of the resulting frequency spectrum provides a rough estimate of the sinewave's fundamental frequency. Next, a bandpass filter designed around this frequency is used to eliminate much of the noise from the samples. Applying the existing four-parameter estimation algorithm to the filtered data, yields a more accurate frequency estimate. Finally, this new value, together with the original (noisy) data record is input to the three-parameter estimation algorithm to determine the remaining sinewave parameters. Simulation results indicate this proposed (new) algorithm not only shows substantial improvement in the accuracy of parameter estimates, but also produces consistent results for higher levels of noise distortion than previous methods have achieved.

Symbolic execution is a powerful technique used to perform various activities such as program testing, formal verification of programs, etc. However, symbolic execution does not deal with indexed variables in an adequate manner. Integration of indexed variables such as arrays into symbolic execution would increase the generality of this technique. We present an original substitution technique that produces array-term-free constraints as a counterargument to the commonly accepted belief that symbolic execution cannot handle arrays. The substitution technique deals with constraints involving array terms with a single aggregate name, array terms with multiple aggregate names, and nested array terms. Our approach to solving constraints involving array terms is based on the analysis of the relationship between the array subscripts. Dataflow dependence analysis of programs involving indexed variables suffers from problems of undecidability. We propose a separation technique in which the array subscript constraints are separated from the loop path constraints. The separation technique suggests that the problem of establishing data dependencies is not as hard as the general loop problem. In this respect, we present a new general heuristic program analysis technique which is used to preserve the properties of the relations between program variables.

Mapping an application program to a parallel architecture can be described as a multidimensional optimization problem. To simplify the problem, we divide the overall mapping process into three sequential substeps: partitioning, allocating, and scheduling, with each step using a few details of the program and architecture description. Due to the difficulty in accurately describing the program and architecture and the fact that each substep uses incomplete information, inaccuracy is pervasive in the real-world mapping process. We hypothesize that the inaccuracy and the use of suboptimal, heuristic mapping methods may greatly affect the mapping or submapping performance and lead to a non-optimal solution. We do not discard the typical approach used by most researchers in which total execution time or speedup is the criterion to evaluate the quality of the mapping. However, we improve on this approach by including the effects of inaccuracy. We believe that, due to the presence of inaccuracy in the mapping process, investigating the impact of inaccuracy on the mapping quality is crucial to achieving good mappings. The motivation of this work is to identify the various inaccuracies during the mapping procedure and explore the sensitivity of mapping quality to the inaccurate parameters. To conduct the sensitivity examination, the Global Cluster partitioning algorithm and some models were used. The models use some program and architecture characteristics, or lower-level meters, to characterize the mapping solution space. The algorithm searches the solution space and makes the decision based on the information provided by the models. The experiments were implemented on a UNIX LAN of Sun workstations for different data flow graphs. The graphs use three parallel programming paradigms: fine grained, coarse-grained, and pipelined styles, to represent some high-level application programs: vector inner product calculation, matrix multiplication, and Gaussian elimination respectively. The experimental results show that varying system behavior affects the accuracy of lower-level meters, and the quality of the mapping algorithm is very sensitive to the inaccuracies.

"November 4, 2002." Includes bibliographical references (leaves 180-814) Applies analytic modelling techniques to the study of agent-based routing algorithms