Li Cheng. / Thesis submitted in: November 2002. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 57-61). / Abstracts in English and Chinese. / Chapter CHAPTER 1 --- INTRODUCTION --- p.1 / Chapter 1.1 --- The Evolution of Ring Network Technologies --- p.1 / Chapter 1.1.1 --- Token Ring Technology --- p.1 / Chapter 1.1.2 --- Resilient Packet Ring Technology --- p.4 / Chapter 1.2 --- Optimal Routing --- p.7 / Chapter 1.3 --- Fairness --- p.8 / Chapter 1.4 --- Outline of Thesis --- p.10 / Chapter CHAPTER 2 --- OPTIMAL ROUTING --- p.11 / Chapter 2.1 --- Throughput Analysis --- p.11 / Chapter 2.2 --- Numerical Results --- p.13 / Chapter CHAPTER 3 --- OPTIMAL FAIR ROUTING --- p.19 / Chapter 3.1 --- Overview --- p.19 / Chapter 3.2 --- Max-min Fair Allocation --- p.19 / Chapter 3.3 --- Proportionally Fair Allocation --- p.32 / Chapter 3.4 --- Numerical Results --- p.33 / Chapter CHAPTER 4 --- TRADEOFF ANALYSIS --- p.40 / Chapter 4.1 --- Tradeoff between Throughput and Max-min Fairness --- p.40 / Chapter 4.2 --- Numerical Results --- p.42 / Chapter 4.3 --- Tradeoff between Throughput and Utility --- p.47 / Chapter 4.4 --- Numerical Results --- p.48 / Chapter CHAPTER 5 --- CONCLUSION --- p.54 / Chapter 5.1 --- Summary --- p.54 / Chapter 5.2 --- Discussion and Future Work --- p.55 / BIBLIOGRAPHY --- p.57

Szeto, Wai Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 81-86). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgements --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations and Aims --- p.1 / Chapter 1.2 --- Thesis Organization --- p.6 / Chapter 2 --- Preliminaries --- p.7 / Chapter 2.1 --- Fundamentals of Music and Terminology --- p.7 / Chapter 2.2 --- Findings in Auditory Psychology --- p.8 / Chapter 3 --- Literature Review --- p.12 / Chapter 3.1 --- Pattern Matching Techniques for Music Information Retrieval --- p.12 / Chapter 3.2 --- Stream Segregation --- p.14 / Chapter 3.3 --- Post-tonal Music Analysis --- p.15 / Chapter 4 --- Proposed Method for Stream Segregation --- p.17 / Chapter 4.1 --- Music Representation --- p.17 / Chapter 4.2 --- Proposed Method --- p.19 / Chapter 4.3 --- Application of Stream Segregation to Polyphonic Databases --- p.27 / Chapter 4.4 --- Experimental Results --- p.30 / Chapter 4.5 --- Summary --- p.36 / Chapter 5 --- Proposed Approaches for Post-tonal Music Analysis --- p.38 / Chapter 5.1 --- Pitch-Class Set Theory --- p.39 / Chapter 5.2 --- Sequence-Based Approach --- p.43 / Chapter 5.2.1 --- Music Representation --- p.43 / Chapter 5.2.2 --- Matching Conditions --- p.44 / Chapter 5.2.3 --- Algorithm --- p.46 / Chapter 5.3 --- Graph-Based Approach --- p.47 / Chapter 5.3.1 --- Graph Theory and Its Notations --- p.48 / Chapter 5.3.2 --- Music Representation --- p.50 / Chapter 5.3.3 --- Matching Conditions --- p.53 / Chapter 5.3.4 --- Algorithm --- p.57 / Chapter 5.4 --- Experiments --- p.67 / Chapter 5.4.1 --- Experiment 1 --- p.67 / Chapter 5.4.2 --- Experiment 2 --- p.68 / Chapter 5.4.3 --- Experiment 3 --- p.70 / Chapter 5.4.4 --- Experiment 4 --- p.75 / Chapter 6 --- Conclusion --- p.79 / Bibliography --- p.81 / A Publications --- p.87

Wang, Yongzhi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (p.68-72). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Abstract Model --- p.7 / Chapter 2.1 --- Request allocation problem --- p.7 / Chapter 2.2 --- Neighbor selection problem --- p.11 / Chapter 3 --- Simulation Model --- p.14 / Chapter 4 --- Load Balancing Algorithms --- p.18 / Chapter 4.1 --- Request allocation --- p.18 / Chapter 4.2 --- Neighbor selection algorithms --- p.24 / Chapter 4.2.1 --- What to measure? --- p.24 / Chapter 4.2.2 --- Timeout-based neighbor selection algorithms --- p.25 / Chapter 4.2.3 --- Periodic neighbor selection algorithms --- p.33 / Chapter 4.2.4 --- Comparison: Timeout-based versus Periodical neighbor selection algorithms --- p.39 / Chapter 4.3 --- Further experiments --- p.41 / Chapter 4.3.1 --- Request window size --- p.41 / Chapter 4.3.2 --- Impact of K --- p.42 / Chapter 4.3.3 --- Adaptive adjustment of the neighbor selection period --- p.43 / Chapter 4.3.4 --- Performance with adequate bandwidth --- p.45 / Chapter 5 --- Minimizing Server´ةs Load --- p.49 / Chapter 6 --- Background Study --- p.56 / Chapter 6.1 --- P2P content distribution system --- p.56 / Chapter 6.1.1 --- P2P File sharing system --- p.56 / Chapter 6.1.2 --- P2P streaming system --- p.59 / Chapter 6.1.3 --- P2P Video on Demand system --- p.61 / Chapter 6.2 --- Congestion control --- p.62 / Chapter 7 --- Conclusion --- p.67 / Bibliography --- p.68

Ma, Ka Lim. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves [110]-117). / Abstracts in English and Chinese. / Chapter 1 --- Radon Transform and Medical Tomography --- p.1 / Chapter 1.1 --- Computed Tomography --- p.2 / Chapter 1.2 --- Emission Computed Tomography --- p.4 / Chapter 1.2.1 --- SPECT --- p.5 / Chapter 1.2.2 --- PET --- p.6 / Chapter 1.3 --- Radon Transform --- p.8 / Chapter 1.3.1 --- Properties of Radon Transform --- p.10 / Chapter 1.3.2 --- Fourier Slice Theorem --- p.11 / Chapter 1.4 --- Research Objective --- p.12 / Chapter 2 --- Popular Tomographic Reconstruction Algorithms --- p.14 / Chapter 2.1 --- Analytic Method --- p.15 / Chapter 2.1.1 --- Direct Fourier Method (DFM) --- p.15 / Chapter 2.1.2 --- Backprojection (BP) --- p.17 / Chapter 2.1.3 --- Backprojection Filtering (BPF) --- p.19 / Chapter 2.1.4 --- Filtered Backprojection (FBP) --- p.21 / Chapter 2.2 --- Iterative Method --- p.23 / Chapter 2.2.1 --- Maximum Likelihood - Expectation Maximization (ML-EM) --- p.25 / Chapter 2.2.2 --- Ordered Subsets Expectation Maximization (OSEM) --- p.27 / Chapter 3 --- Consistent Reconstruction --- p.30 / Chapter 3.1 --- Directional Filter Bank (DFB) --- p.30 / Chapter 3.1.1 --- Interpolation in horizontal function space --- p.32 / Chapter 3.1.2 --- Directional Multiresolution Analysis --- p.33 / Chapter 3.1.3 --- Iterated Filter Bank Equivalence --- p.36 / Chapter 3.1.4 --- Vertical Directional Function Space --- p.38 / Chapter 3.1.5 --- Summary --- p.40 / Chapter 3.2 --- Reconstruction Scheme --- p.42 / Chapter 3.2.1 --- Choices for basis function 6m --- p.43 / Chapter 3.2.2 --- Choices for coordinate mapping function wm --- p.46 / Chapter 3.2.3 --- Summary --- p.49 / Chapter 3.3 --- Experiment --- p.49 / Chapter 3.3.1 --- Experiment for consistent reconstruction with different choices --- p.50 / Chapter 3.3.2 --- Experiment for comparison with different reconstruction methods --- p.54 / Chapter 3.4 --- Conclusion --- p.56 / Chapter 4 --- Tomographic Denoising --- p.57 / Chapter 4.1 --- SURE-LET and PURE-LET denoising --- p.59 / Chapter 4.1.1 --- SURE-LET --- p.60 / Chapter 4.1.2 --- PURE-LET --- p.62 / Chapter 4.2 --- Experiment --- p.64 / Chapter 4.2.1 --- Experiment on SURE-LET Denoising --- p.65 / Chapter 4.2.2 --- Experiment on PURE-LET Denoising --- p.69 / Chapter 4.2.3 --- Conclusion --- p.76 / Chapter 5 --- Sinogram Retrieval --- p.77 / Chapter 5.1 --- Sinogram Retrieval Method --- p.78 / Chapter 5.1.1 --- MATLAB Radon Function --- p.79 / Chapter 5.1.2 --- Subordinate Gradient (SG) Algorithm --- p.81 / Chapter 5.1.3 --- Orthonormal Subordinate Gradient (OSG) Algorithm --- p.81 / Chapter 5.2 --- Experiment --- p.84 / Chapter 5.2.1 --- Limitation of Sinogram Retrieval --- p.84 / Chapter 5.2.2 --- Comparison of Sinogram Retrieval Algorithms --- p.86 / Chapter 5.2.3 --- Embedded in Tomographic Reconstruction --- p.88 / Chapter 5.2.4 --- Embedded in Tomographic Denoising --- p.90 / Chapter 5.3 --- Conclusion --- p.96 / Chapter 6 --- Conclusion --- p.97 / Chapter 6.1 --- Summary --- p.97 / Chapter 6.1.1 --- Tomographic Reconstruction --- p.97 / Chapter 6.1.2 --- Tomographic Denoising --- p.98 / Chapter 6.1.3 --- Sinogram Retrieval --- p.98 / Chapter 6.2 --- Future Research --- p.99 / Chapter 6.2.1 --- Tomographic Reconstruction --- p.99 / Chapter 6.2.2 --- Tomographic Denoising --- p.99 / Chapter 6.2.3 --- Sinogram Retrieval --- p.99 / Chapter A --- Examples of Radon Transform --- p.100 / Chapter B --- Experimental Phantom Image --- p.104 / Chapter C --- Results of sinogram retrieval experiments --- p.107 / Bibliography --- p.110

Excessive high-frequency jitter or low-frequency wander can create problems within synchronous transmission systems and must be kept within limits to ensure reliable network operation. The emerging Synchronous Optical NETwork (SONET) introduces additional challenges for jitter and wander attenuation equipment (called desynchronizers) when used to carry payloads from the existing Plesiochronous Digital Hierarchy (PDH), such as the DS3. The difficulty is primarily due to the large phase transients resulting from the pointer-based justification technique employed by SONET (called Pointer Justification Events or PJEs). While some previous desynchronization techniques consider the buffer level in their control actions, none has explicitly considered wander generation. Instead, compliance with jitter, wander, and buffer-size constraints have typically been met implicitly--through testing and tuning of the Phase Locked Loop (PLL) controller. We investigated a fuzzy/rule-based solution to this desynchronization/constraint-satisfaction problem. But rather than mapping the input state to an action, as is done in standard fuzzy logic, our controller maps a state and a candidate action to a desired result. In other words, this control paradigm employs prediction to evaluate which of a set of candidate actions would result in the "best" predicted performance. Before the controller could predict an action's affect on buffer and wander levels, appropriate models were required. The model of the buffer is simply the integral of the frequency difference between the input and output of the PLL, and a novel MTIE Constraint Envelope technique was developed to evaluate future wander performance. We show that a predictive knowledge-based controller is capable of achieving the following three objectives: (1) Reduce jitter implicitly by avoiding unnecessary frequency changes such that the jitter limits specified in relevant standards are met, (2) Explicitly satisfy both buffer-level and wander (MTIE) constraints by trading off performance in one to meet the hard limit of the other, (3) When both buffer-level and wander constraints are in danger of violation and cannot be satisfied simultaneously, maintain the preferred constraint by sacrificing the other. We also show that the computation required for this control algorithm is easily within the reach of modern microprocessors.

A number of recent developments has increased the desirability of using exclusive OR (XOR) gates in the synthesis of switching functions. This has, in turn, led naturally to an increased interest in algorithms for the minimization of Exclusive-Or Sum of Products (ESOP) forms. Although this is an active area of research, it is not nearly as developed as the traditional Sum of Products forms. Computer programs to find minimum ESOPs are not readily available and those that do exist are impractical to use as investigative tools because they are too slow and/or require too much memory. A practical tool would be easy enough to use (faster/smaller) so that it could be run many times to explore the solution space of the minimization problem as well as to provide a baseline of comparison. This thesis develops and investigates such a tool.

In this thesis, we describe an architecture-driven fitting algorithm for an Application-Specific EPLD, the CY7C361, from Cypress Semiconductor. Traditional placement and routing tools for PLDs perform placement and routing separately. Several placement possibilities are created and the router tries to realize the connections between the physical locations of the cells on the chip. The Cypress CY7C361 has a very unique chip architecture with a highly limited connectivity between the physical cells. Therefore, it is necessary to consider the mutability when the placement of cells is performed. The combination of the two stages is called fitting. The specific architecture-dependent constraints, imposed on the connectivity of the CY7C361 chip were used to develop a hierarchical partitioning structure of the algorithm. This approach limits very effectively the solution space in the early stage of the search for a solution of the fitting problem. The partitioning approach for the fitting algorithm is not limited on the Cypress CY7C361. It can be applied to other architectures with similar connectivity restrictions, too.

The goal of parallel processing is to achieve high speed computing by partitioning a program into concurrent parts, assigning them in an efficient way to the available processors, scheduling the program and then executing the concurrent parts simultaneously. In the past researchers have combined the allocation of tasks in a program and scheduling of those tasks into one operation. We define scheduling as a process of efficiently assigning priorities to the already allocated tasks in a program. Assignment of priorities is important in cases when more than one task at a processor is ready for execution. Most heuristics for scheduling consider certain parameters of the architecture and the program. These parameters could be the execution time of each operation in a program, the number of processors, etc. The impact of ignoring interprocessor communication (IPC) when ordering parallel tasks has, however, not been well studied.

The effectiveness of the Additive Correction Multigrid (ACM) algorithm, a line-byline Tri-diagonal Matrix Algorithm (TDMA), and simple Gauss-Seidel (GS) iteration in numerical heat transfer analysis is investigated on a conventional single processor computer and on a distributed memory parallel computer. The performance of these methods is studied by solving a two-dimensional, steady heat conduction problem. The execution time of ACM on a single processor is proportional to the number of unknowns to the 1.5 power. This is in contrast to the execution time of the TDMA for which the execution time is proportional to the number of unknowns to the 2.0 power. The GS , TDMA and ACM algorithms are adapted to a model IPSC2 Intel hypercube which has a 32 processing nodes each with 8 MBytes oflocal memory. Because GS is a local method, it has almost perfect speed up, but it also converges more slowly than TDMA, The TDMA, on the other hand, is affected by domain decomposition to a greater extent than GS. As the number of processors used to solve the problem is increased, the execution times for GS and TDMA are essentially equal. Solving the model problem with 32 processors on a 192x192 grid resulted in parallel efficiencies of 95%, 80% and 78% for the GS, TDMA, and ACM algorithms, respectively. Though the parallel efficiency of ACM was the lowest of the three, the parallel ACM algorithm required an order of magnitude less time to solve the model than either parallel GS or parallel TDMA without multigrid.

Transaction logging is an integral part of ensuring proper transformation of data from one state to another in modern data management. Because of this, the throughput of the logging subsystem can be critical to the throughput of an application. The purpose of this research is to break the log bottleneck at minimum cost. We first present a model for evaluating a logging subsystem, where a logging subsystem is made up of a log device, a log backup device, and the interconnect algorithm between the two, which we term the log backup method. Included in the logging model is a set of criteria for evaluating a logging subsystem and a system for weighting the criteria in order to facilitate comparisons of two logging subsystem configurations to determine the better of the two. We then present an evaluation of each of the pieces of the logging subsystem in order to increase the bandwidth of both the log device and log backup device, while selecting the best log backup method, at minimum cost. We show that the use of striping and RAID is the best alternative for increasing log device bandwidth. Along with our discussion of RAID, we introduce a new RAID algorithm that is designed to overcome the performance problems of small writes in a RAID log. In order to increase the effective bandwidth of the log backup device, we suggest the use of inexpensive magnetic tape drives and striping in the log backup device, where the bandwidth of the log backup device is increased to the point that it matches the bandwidth of the log device. For the log backup interconnect algorithm, we present the novel approach of backing up the log synchronously, where the log backup device is essentially a mirror of the log device, as well as evaluating other log backup interconnect algorithms. Finally, we present a discussion of a prototype implementation of some of the ideas in the thesis. The prototype was implemented in a commercial database system, using a beta version of INFORMIX-OnLine Dynamic Server™ version 6.0.