published_or_final_version / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Computer Science / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Computer Science / Doctoral / Doctor of Philosophy

The study of multicomputer interconnection networks is an important area of research in parallel processing. We introduce vertex-symmetric Hamming-group graphs as a model to design a wide variety of network topologies including the hypercube network.

The goal of a parallel algorithm is to solve a single problem using multiple processors working together and to do so in an efficient manner. In this regard, there is a need to categorize strategies in order to solve broad classes of problems with similar structures and requirements. In this dissertation, two parallel algorithm design strategies are considered: linked list ranking and parentheses matching.

by Vincent Sau Yan Yiu. / "April 2000." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2000. / Includes bibliographical references (p. 126-131). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

by Wong, Shing-hung Lewis. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1993. / Includes bibliographical references. / Acknowledgements / Abstract / Chapter Chapter 1 --- Introduction --- p.1-1 / Chapter 1.1 --- Background --- p.1-1 / Chapter 1.1.1 --- Technology Advancement --- p.1-1 / Chapter 1.1.2 --- Lack of Multiprocessor Standards --- p.1-1 / Chapter 1.1.3 --- Demand for Greater Processing Power --- p.1-3 / Chapter 1.1.4 --- Parallel Computing --- p.1-3 / Chapter 1.1.5 --- Research Support --- p.1-4 / Chapter 1.2 --- Related works --- p.1-4 / Chapter 1.3 --- "Expectations : OS dependent, but hardware independent" --- p.1-8 / Chapter 1.4 --- Summary --- p.1-8 / Chapter Chapter 2 --- Overall Design --- p.2-1 / Chapter 2.1 --- An Overview --- p.2-1 / Chapter 2.2 --- Common models --- p.2-3 / Chapter 2.2.1 --- The Master-Slave model --- p.2-3 / Chapter 2.2.2 --- Floating Executives Using Giant Locks --- p.2-4 / Chapter 2.2.3 --- Multithreaded Kernels (or Homogeneous Model) --- p.2-6 / Chapter 2.3 --- My model --- p.2-7 / Chapter 2.3.1 --- Multitaskers and my Object Scheduler --- p.2-8 / Chapter 2.3.2 --- Lower Layer: Object Scheduler & Message-box Handler --- p.2-10 / Chapter 2.3.3 --- "Upper Layer: ""C++*"" Language" --- p.2-12 / Chapter 2.4 --- Summary --- p.2-15 / Chapter Chapter 3 --- Design & Implementation Details --- p.3-1 / Chapter 3.1 --- Design Considerations --- p.3-1 / Chapter 3.1.1 --- Possible Scheduling Policies --- p.3-1 / Chapter 3.1.2 --- Interface to UNIX® OS --- p.3-5 / Chapter 3.2 --- Design and Implementation Details --- p.3-9 / Chapter 3.2.1 --- Lower Layer: Object Scheduler & Message-box Handler --- p.3-10 / Chapter 3.2.2 --- "Upper Layer: ""C++*""Language" --- p.3-17 / Chapter 3.3 --- Summary --- p.3-23 / Chapter Chapter 4 --- Simulation Results --- p.4-1 / Chapter 4.1 --- Execution of an application --- p.4-1 / Chapter 4.2 --- Design Simulation --- p.4-2 / Chapter 4.2.1 --- Simulation Experiment Design --- p.4-3 / Chapter 4.2.2 --- Simulation Results --- p.4-4 / Chapter 4.2.3 --- Discussion --- p.4-6 / Chapter 4.3 --- Summary --- p.4-7 / Chapter Chapter 5 --- Sample Applications --- p.5-1 / Chapter 5.1 --- A Distributed Object-Oriented Visualization Package --- p.5-1 / Chapter 5.1.1 --- Design Objectives --- p.5-1 / Chapter 5.1.2 --- Design Methodology --- p.5-2 / Chapter 5.1.3 --- Class Hierarchy Relation --- p.5-2 / Chapter 5.1.4 --- Object Hierarchy (Contain) Relation --- p.5-4 / Chapter 5.1.5 --- Class Specifications --- p.5-5 / Chapter 5.1.6 --- Parallel Algorithms --- p.5-7 / Chapter 5.1.7 --- Speed Up of Distributed Approach --- p.5-17 / Chapter 5.1.8 --- Grain Size Considerations --- p.5-19 / Chapter 5.1.9 --- Performance Evaluation --- p.5-19 / Chapter 5.2 --- Fractal Evaluation --- p.5-28 / Chapter 5.2.1 --- Unit Machine --- p.5-29 / Chapter 5.2.2 --- Speed Up --- p.5-29 / Chapter 5.2.3 --- Grain Size Considerations --- p.5-33 / Chapter 5.5 --- Summary --- p.5-35 / Chapter Chapter 6 --- Conclusion --- p.6-1 / Reference --- p.R-1 / "Appendix 1 User guide of ""C++*""" --- p.A-1 / Chapter 1 --- System Requirements --- p.A-1 / Chapter 2) --- Installation --- p.A-1 / Chapter 3) --- Usage --- p.A-1 / Chapter 4) --- Programming Interfaces --- p.A-2 / Chapter 5) --- Limitation --- p.A-2 / "Appendix 2 Coding of class "" Parallel""" --- p.A-4 / "Appendix 3 A Simple Sample Application of "" C++*""" --- p.A-17

Shum Yu Hing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1994. / Includes bibliographical references (leaves 140-143). / ABSTRACT --- p.1 / Chapter 1. --- INTRODUCTION / Chapter 1.1. --- Fourier Analysis --- p.3 / Chapter 1.2. --- Wavelet Analysis --- p.6 / Chapter 1.3. --- Parallelization --- p.10 / Chapter 1.3.1. --- Data Dependency Analysis / Chapter 2. --- LITERATURE SURVEY / Chapter 2.1. --- One Dimensional Fast Wavelet Transform (Discrete) --- p.13 / Chapter 2.2. --- Shared Memory Architecture : Parallel Virtual Machine (PVM) / Chapter 2.3. --- Distributed Memory Architecture : Massively Parallel Machine (DECmpp) --- p.21 / Chapter 3. --- THEORY / Chapter 3.1. --- Parallel Processing / Chapter 3.1.1. --- Amdahl ´ةs Law --- p.25 / Chapter 3.1.2. --- Quality Factor --- p.31 / Chapter 3.2. --- Parallel Architecture / Chapter 3.2.1. --- Pipelining --- p.32 / Chapter 3.2.2. --- Vector Processors --- p.34 / Chapter 3.2.3. --- Multiprocessor --- p.34 / Chapter 3.2.4 --- Array Processors --- p.36 / Chapter 3.2.5. --- Systolic Array Processing --- p.37 / Chapter 3.2.6. --- Granularity --- p.40 / Chapter 3.2.7. --- Load Balancing & Throughput --- p.42 / Chapter 3.3. --- Parallel Programming --- p.43 / Chapter 3.4. --- Parallel Numerical Algorithm / Chapter 3.4.1. --- Parallelism Within a Statement --- p.44 / Chapter 3.4.2. --- Parallelism Between Statements --- p.47 / Chapter 4. --- IMPLEMENTATION / Chapter 4.1. --- Sequential Version --- p.49 / Chapter 4.2. --- Parallel Version / Chapter 4.2.1. --- Matrix Representation of Wavelet Transform / Chapter 4.2.1.1. --- Decomposition --- p.52 / Chapter 4.2.1.2. --- Reconstruct ion --- p.55 / Chapter 4.2.2. --- Parallel Virtual Machine (PVM) / Chapter 4.2.2.1. --- Parallel Algorithm / Chapter (a) --- HOST --- p.56 / Chapter (b) --- NODE --- p.57 / Chapter 4.2.2.2. --- Flowcharts --- p.59 / Chapter 4.2.2.3. --- Timing Model Analysis --- p.65 / Chapter 4.2.2.4 --- Quality Factor / Chapter (a) --- Decomposition --- p.71 / Chapter (b) --- Reconstruction --- p.72 / Chapter 4.2.3. --- Massively Parallel Machine - DECmpp --- p.73 / Chapter 4.2.3.1. --- Parallel Algorithm for ACU & PEs / Chapter 4.2.3.2. --- Flowcharts --- p.75 / Chapter 4.2.3.3. --- Timing Model Analysis / Chapter (a) --- Communication Strategy --- p.77 / Chapter (b) --- Decomposition --- p.78 / Chapter (c) --- Reconstruct ion --- p.87 / Chapter 4.2.3.4. --- Quality Factor / Chapter (a) --- Decomposition --- p.89 / Chapter (b) --- Reconstruction --- p.89 / Chapter 4.2.3.5. --- Mapping --- p.92 / Chapter 5. --- RESULT / Chapter 5.1. --- Parallel Virtual Machine (PVM) / Chapter 5.1.1. --- Sequential Version --- p.93 / Chapter 5.1.2. --- Parallel Version --- p.103 / Chapter 5.2. --- Massively Parallel Machine - DECmpp / Chapter 5.2.1. --- Sequential Vers ion --- p.104 / Chapter 5.2.2. --- Parallel Version --- p.110 / Chapter 5.3. --- Output File Generated from both machines --- p.118 / Chapter 6. --- DISCUSSION / Chapter 6.1. --- Application on real time situation --- p.123 / Chapter 6.2. --- Two dimensional or Multidimensional case --- p.123 / Chapter 6.3. --- Block Algorithm Approach / Chapter 6.3.1. --- Blocked --- p.124 / Chapter 6.3.2. --- Row Wrapped --- p.126 / Chapter 6.4. --- Memory Requirement --- p.127 / Chapter 6.5. --- Signal Size Prediction / Chapter 6.5.1. --- Method A --- p.131 / Chapter 6.5.2. --- Method B --- p.133 / Chapter 7. --- CONCLUSION --- p.134 / Chapter 8. --- FUTURE MODIFICATION --- p.138 / REFERENCE --- p.140 / LISTING --- p.144 / APPENDIX I - Technical Information of PVM --- p.145 / Chapter II - --- Technical Information of DECmpp --- p.152 / Chapter III - --- Some Tips/Guide --- p.165

by Wong Tin-Lam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 70-73). / Abstract --- p.ii / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Scheduling Problems --- p.1 / Chapter 1.2 --- Literature Review --- p.4 / Chapter 1.2.1 --- Sized Multiprocessor Task Scheduling --- p.5 / Chapter 1.2.2 --- Fixed Multiprocessor Task Scheduling --- p.6 / Chapter 1.2.3 --- Set Multiprocessor Task Scheduling --- p.8 / Chapter 1.3 --- Organization of Thesis --- p.10 / Chapter 2 --- Overview --- p.11 / Chapter 2.1 --- Machine Environment --- p.11 / Chapter 2.2 --- The Jobs and Their Requirements --- p.12 / Chapter 2.3 --- Assumptions --- p.13 / Chapter 2.4 --- Constraints --- p.14 / Chapter 2.5 --- Objective --- p.15 / Chapter 2.6 --- An Illustrative Example --- p.17 / Chapter 2.7 --- NP-Hardness --- p.20 / Chapter 3 --- Methodology --- p.22 / Chapter 3.1 --- Dynamic Programming --- p.22 / Chapter 3.1.1 --- Problem Analysis --- p.24 / Chapter 3.2 --- Key Idea to solve the problem --- p.27 / Chapter 3.3 --- Algorithm --- p.28 / Chapter 3.3.1 --- Phase 1 --- p.28 / Chapter 3.3.2 --- Phase 2 --- p.37 / Chapter 4 --- Extensions --- p.46 / Chapter 4.1 --- "Polynomially Solvable Cases P2 --- p.46 / Chapter 4.1.1 --- Dynamic Programming --- p.47 / Chapter 4.2 --- "Set Problem P2/setj,prmp/TmaX" --- p.55 / Chapter 4.2.1 --- Processing times for set jobs --- p.56 / Chapter 4.2.2 --- Algorithm --- p.58 / Chapter 4.3 --- k´ؤMachine Problem with only two types of jobs --- p.64 / Chapter 5 --- Conclusion and Future Work --- p.67 / Chapter 5.1 --- Conclusion --- p.67 / Chapter 5.2 --- Some Future Work --- p.68 / Bibliography --- p.70

Yan, Kan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 64-[66]). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese.