This dissertation presents a new framework, trace-automata, for verifying hybrid systems. In addition, a simple, general theory of abstraction is presented, based on the idea of approximations that are liberal or conservative with respect to an abstraction function. This theory gives rise to a sound technique whereby hybrid systems are verified by constructing discrete approximations of both the implementation and the specification, and verifying that the approximate implementation satisfies the approximate specification. Trace-automata are language accepting, infinite tape automata, extended to allow multiple tapes, and to allow tapes that consist of continuous traces over the reals, as well as tapes that consist of sequences of discrete symbols. Hybrid systems are represented by automata that read some continuous tapes and some discrete tapes. Trace-automata are used to represent both the implementation and the specification of the system to be verified. Verification corresponds to demonstrating that the language accepted by the implementation is contained in that accepted by the specification. Hybrid systems are verified by constructing and verifying discrete approximations. Abstraction functions map continuous traces to discrete sequences. A liberal approximation of the system implementation is verified against a conservative approximation of the system specification. From this verification, it can be concluded that the original hybrid model satisfies the original specification. The dissertation describes a general technique for constructing discrete, liberal approximations of trace-automata representing differential equations and inclusions. In addition, trace-automata themselves can encode abstraction functions, with the result that trace-automata language containment can also be used to establish that an approximation is liberal or conservative as the case may be. These techniques are illustrated with an example verification based upon the Philips Audio Control Protocol with two agents, each capable of both transmitting and receiving. The verification is novel in that it is based upon a detailed model of the analog electrical behaviour of the bus. / Science, Faculty of / Computer Science, Department of / Graduate

No description available.

This project explores the interactions of young children with computers in their homes. It focuses on: resources available and what affordances these enable; socio-cultural contexts, discourses and family practices; nature of the use and affordances children perceive; and how school experiences differ from those at home and the impact of teachers' discourses about computing. Findings were: common activities comprised game playing, editing and decorating texts and using information texts; gender and socio-economic differences interacted with varying rules, resources, discourses, affordances, and family use and expertise; parental discourses and resources combined to generate key affordances of the computer as toy and tool; parental discourses revealed different conceptions of childhood and computers; children’s patterns of learning and use are relatively consistent across age, gender and family background – they learn by exploring and the dominant affordance is the computer as playable; teachers’ discourses and conceptions lead to the marginalisation of computer use within the curriculum; at school, children have less access, control and time to use computers in ways that allow them to draw on the expertise and approaches they have developed at home. Theories are developed to show how children come to perceive the computer as playable, and how parents’ and teachers’ discourses position computing as marginal to the curriculum. The other issues relate to conceptions of learning, types of learning that computers afford, and the possibility that children’s approaches to learning are changing as a result of their interactions with computers / Doctor of Philosophy (PhD)

Parallel loops are one of the main sources of parallelism in scientific applications, and many parallel loops do not have a uniform iteration execution time. To achieve good performance for such applications on a parallel computer, iterations of a parallel loop have to be assigned to processors in such a way that each processor has roughly the same amount of work in terms of execution time. A parallel computer with a large number of processors tends to have distributed-memory. To run a parallel loop on a distributed-memory machine, data distribution also needs to be considered. This research investigates the scheduling of non-uniform parallel loops on both shared-memory and distributed-memory parallel computers. We present Safe Self-Scheduling (SSS), a new scheduling scheme that combines the advantages of both static and dynamic scheduling schemes. SSS has two phases: a static scheduling phase and a dynamic self-scheduling phase that together reduce the scheduling overhead while achieving a well balanced workload. The techniques introduced in SSS can be used by other self-scheduling schemes. The static scheduling phase further improves the performance by maintaining a high cache hit ratio resulting from increased affinity of iterations to processors. SSS is also very well suited for distributed-memory machines. We introduce methods to duplicate data on a number of processors. The methods eliminate data movement during computation and increase the scalability of problem size. We discuss a systematic approach to implement a given self-scheduling scheme on a distributed-memory. We also show a multilevel scheduling scheme to self-schedule parallel loops on a distributed-memory machine with a large number of processors to eliminate the bottleneck resulting from a central scheduler. We proposed a method using abstractions to automate both self-scheduling methods and data distribution methods in parallel programming environments. The abstractions are tested using CHARM, a real parallel programming environment. Methods are also developed to tolerate processor faults caused by both physical failure and reassignment of processors by the operating system during the execution of a parallel loop. We tested the techniques discussed using simulations and real applications. Good results have been obtained on both shared-memory and distributed-memory parallel computers. / Graduation date: 1994

Thesis (M.S.)--Rochester Institute of Technology, 2009. / Typescript. Includes bibliographical references (leaves 54-56).

No description available.

(Uncorrected OCR) Abstract of Thesis entitled 'Virtual Links for Multicomputers' Submitted by Siu Kit Wai for the degree of Master of Philosophy at Univsersity of Hong Kong in October 1996 In order to increase computation power, multiple autonomous computers or processors are connected to form a multicomputer. The performance boost is the result of exploiting in parallel the processing power available in individual processors. Parallel processing, however, requires the cooperation among the processors, which implies interprocessor communication. The efficiency of such communications is limited by the bandwidth and number of communication channels between directly connected processors. Multiple processes on a processor share a few hardware communication links/channels to communication with processes executing on a different processor. Effective and efficient sharing of channels is important for the overall system performance; hence it is important that the sharing be properly managed. When the sharing is not provided by the hardware, it can be provided in software at system level. Without a managing component, processes need to be programmed to flight for and gain exclusive access to the communication links. This is usually not effective, error-prone, and could reduce the overall performance of processes executing in the processor. Flexibility is a main advantage of providing a channel-sharing mechanism at system level. Parameters such as packet size, and configuration of the system can be customized and tuned to meet the communication characteristics of different applications. In this project, we investigate how link sharing can be provided at system level. Our approach is based on idea of virtual links. The system is designed to be as transparent and easy to be used as possible. We will discuss how different parameters and configurations affect the system functionality and performance. We also compare this software solution to other existing solutions including a hardware solution. ii / abstract / toc / Computer Science / Master / Master of Philosophy

published_or_final_version / English Studies / Master / Master of Arts

Qian Zhengfeng. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 127-129). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Groundwork --- p.1 / Chapter 1.1 --- Introduction --- p.1 / Chapter 1.2 --- Exchange Patterns --- p.5 / Chapter 1.3 --- Multistage Networks --- p.9 / Chapter 1.3.1 --- Multistage Networks --- p.9 / Chapter 1.3.2 --- Banyan-type Networks --- p.11 / Chapter 1.4 --- Networks of Sorting Cells --- p.15 / Chapter 1.5 --- Symbolic Representation and Matrix Representation --- p.19 / Chapter 1.5.1 --- Symbolic Representation of a Multistage Interconnection Network --- p.19 / Chapter 1.5.2 --- Symbolic Representation of a Network of Sorting Cells --- p.21 / Chapter 1.5.3 --- Matrix Representation of a Network of Sorting Cells --- p.22 / Chapter 1.6 --- Summary --- p.24 / Chapter Chapter 2 --- Construction of Generalized Bitonic Sorters by Merging Rotated Monotonic Sequences --- p.25 / Chapter 2.1 --- Merging Networks --- p.25 / Chapter 2.1.1 --- Recursive 2-stage Construction --- p.26 / Chapter 2.1.2 --- UC/CU Non-blocking Switches --- p.35 / Chapter 2.1.3 --- Circular Sorters and Merging Networks --- p.41 / Chapter 2.2 --- Construction of Generalized Bitonic Sorters --- p.48 / Chapter 2.2.1 --- Bitonic Ar-sorters and Bitonic Dr-sorters --- p.48 / Chapter 2.2.2 --- Algorithms for Construction of Generalized Bitonic Sorters by Merging Rotated Monotonic Sequences --- p.51 / Chapter 2.3 --- Summary --- p.73 / Chapter Chapter 3 --- Construction of Generalized Bitonic Sorters by Cross-k Cell Rearrangement --- p.74 / Chapter 3.1 --- Cross-k Cell Rearrangement on a Multistage Network --- p.74 / Chapter 3.1.1 --- Intra-stage Cell Rearrangement --- p.74 / Chapter 3.1.2 --- Equivalence of Networks --- p.77 / Chapter 3.1.3 --- Cross-k Cell Rearrangement --- p.80 / Chapter 3.2 --- Construction of Generalized Bitonic Sorters --- p.85 / Chapter 3.3 --- Summary --- p.99 / Chapter Chapter 4 --- Redundancy of the Bitonic Network --- p.100 / Chapter 4.1 --- Counting of Identified Generalized Bitonic Sorters --- p.100 / Chapter 4.2 --- Redundancy of the Bitonic Network --- p.110 / Epilogue --- p.112 / Appendix C Program for Exhaustive Search of 8×8 Generalized Bitonic Sorters --- p.113 / References --- p.127

No description available.