Inaug.-Diss.--Bonn. / Extra t.p. with thesis statement inserted. Bibliography: p. 54.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1970. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

Thesis (M.S.)--Rochester Institute of Technology, 2007. / Typescript. Includes bibliographical references (leaves 146-149).

In this thesis, we consider the problem of decontaminating networks from black viruses (BVs) with a team of mobile agents, using parallel strategies. The BV is a harmful process whose initial location is unknown a priori. It destroys any agent arriving at the network site where it resides and, once triggered, it spreads to all the neighboring sites, creating copies of itself, thus increasing its presence in the network. To eliminate a virus present in a node, an agent has to move on that node; however, once the disinfection is performed, the agent is destroyed (i.e., it becomes inactive and cannot operate anymore). Existing literature has proposed sequential strategies that minimize the spread of the virus, such techniques are however quite inefficient in terms of time complexity. Instead of exploring the network sequentially, we propose to employ a group of agents that cooperate to follow a collective protocol to explore the network simultaneously. In this way, we dramatically reduce the decontamination time, still keeping the spread (and the number of agents loss) asymptotically optimal. In the thesis, various protocols are proposed in meshes, tori, and chordal rings following the monotonicity principle (i.e., once a node is disinfected we prevent it from being recontaminated). Finally, a solution is proposed also for the general case of the arbitrary topology. We analyze theoretically the cost of all our solutions for special topologies showing the advantages of our strategies with respect to the existing ones. In the case of the arbitrary topology, we conduct experimental analysis to assess the performance of our solution, confirming its efficiency. In all cases, our strategies significantly improve time while maintaining asymptotically optimal spread and agent losses.

No description available.

No description available.

A fundamental problem in multithreaded parallel programs is the partial serialization that is imposed due to the presence of mutual exclusion variables or critical sections. In this work we investigate a model that considers the threads consisting of an equal number L of functional blocks, where each functional block has the same duration and either accesses a critical section or executes non-critical code. We derived formulas to estimate the average time spent in a critical section in presence of synchronization barrier and in absence of it. We also develop and establish the optimality of a fast polynomial-time algorithm to find a schedule with the shortest makespan for any number of threads and for any number of critical sections for the case of L = 2. For the general case L > 2, which is NP-complete, we present a competitive heuristic and provide experimental comparisons with the ideal integer linear programming (ILP) formulation.

Made available in DSpace on 2014-06-12T15:57:17Z (GMT). No. of bitstreams: 2 arquivo3161_1.pdf: 1109714 bytes, checksum: 63bb826b538cafab9528cb9cb8274bdc (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Com a adoção pelo mercado dos processadores de nucleos multiplos, o uso de threads em Java se torna cada vez mais proveitoso. O desenvolvimento de sistemas paralelos e, entretanto, uma tarefa que poucos desenvolvedores estão capacitados a enfrentar. Dado esse contexto, foi desenvolvida uma abordagem de paralelizaçaao de programas java baseada em leis de transformação, com o intuito de facilitar esse processo e permitir uma paralelização sistemática. O primeiro passo da abordagem utiliza leis de transformação para converter um programa Java em uma forma normal que utiliza um conjunto restrito de recursos da linguagem. Neste passo, foram definidas leis de transformação adaptadas de trabalhos anteriores, assim como novas leis foram propostas. A partir de um programa na forma normal, são utilizadas regras de transformação focadas em introduzir paralelismo. Após a aplicação dessas regras de acordo com a estretégia desenvolvida, um programa paralelo e produzido. Dois casos de estudo foram realizados para validar a abordagem: calculo de series de Fourier e o algoritmo de criptografia IDEA. Ambos códigos foram obtidos do Java Grande Benchmark Suite. A execução dos estudos de caso comprova o êxito da abordagem em melhorar a performance do cóodigo original

The systolic array research was pioneered by H. T. Kung and C. E. Leiserson. Systolic arrays are special purpose synchronous architectures consisting of simple, regular and modular processors which are regularly interconnected to form an array. Systolic arrays are well suited for computational bound problems in Linear Algebra. In this thesis, the numerical problems, especially iterative algorithms are chosen and implemented on the linear systolic array. same.

A new style of abstraction for program development, based on the concept of algorithmic skeletons, has been proposed in the literature. The programmer is offered a variety of independent algorithmic skeletons each of which describe the structure of a particular style of algorithm. The appropriate skeleton is used by the system to mould the solution. Parallel programs are particularly appropriate for this technique because of their complexity. This thesis investigates algorithmic skeletons as a method of hiding the complexities of parallel programming from the user, and for guiding them towards efficient solutions. To explore this approach, this thesis describes the implementation and benchmarking of the divide and conquer and task queue paradigms as skeletons. All but one category of problem, as implemented in this thesis, scale well over eight processors. The rate of speed up tails off when there are significant communication requirements. The results show that, with some user knowledge, efficient parallel programs can be developed using this method. The evaluation explores methods for fine tuning some skeleton programs to achieve increased efficiency.