No description available.

This thesis describes fast and deterministic deadlock avoidance methods that are easily applicable to real-time MultiProcessor System-on-a-Chip (MPSoC) design. This thesis first describes the proofs of the correctness of Parallel Deadlock Detection Algorithm (PDDA) and the run-time complexity of its hardware implementation in the Deadlock Detection Unit (DDU), proposed previously. The DDU has a worst-case run-time of O(min(m,n)) where m and n are the numbers of resources and processes, respectively. This thesis also provides detailed explanation and mathematical analysis of PDDA and the DDU along with examples, as well as extensive performance comparisons among PDDA in software, the DDU and an O(m x n) deadlock detection algorithm. The DDU is 100X or more faster than software implementations of deadlock detection algorithms. This thesis secondly proposes a novel deadlock avoidance algorithm and its hardware implementation in the Deadlock Avoidance Unit (DAU) that provides very fast and automatic deadlock avoidance in an MPSoC with multiple single-instance resources. The DAU avoids deadlock by not allowing any grant or request that leads to a deadlock. In case of livelock in an attempt to avoid deadlock, the DAU asks one of the processes involved in the livelock to release resource(s) so that such a livelock can also be resolved. We simulated two synthetic applications that can benefit from the DAU and demonstrated that the DAU avoids deadlock approximately 300X faster than its software implementation does. This thesis also proposes a novel Parallel Bankers Algorithm (PBA), a parallelized version of the Banker's Algorithm, and its hardware implementation in PBA Unit (PBAU) that provides fast, automatic deadlock avoidance for multiple-instance resource systems. The run-time complexity of the PBA is O(n) with the best case of O(1). The PBAU is about 1000X faster than the Banker's Algorithm in software and achieves in a particular example a 19% speed-up of application execution time. We believe that our approaches initiate a paradigm shift in the context of deadlock solutions for MPSoC from sole software to hardware/software partitioned solutions that enable a distribution of part of the burden imposed on processors to a low cost, fast hardware IP core exploiting full parallelism.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-07-12T12:30:10Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO (2015-08-17) - RAFAEL BRANDAO LOBO.pdf: 1015468 bytes, checksum: d543b6f16adc4ce4d3aa4d59c8d546ff (MD5) / Made available in DSpace on 2016-07-12T12:30:10Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO (2015-08-17) - RAFAEL BRANDAO LOBO.pdf: 1015468 bytes, checksum: d543b6f16adc4ce4d3aa4d59c8d546ff (MD5) Previous issue date: 2015-07-17 / CAPEs / Deadlocks are a common type of concurrency bug. When a deadlock occurs, it is difficult to clearly determine whether there is an actual deadlock or if the application is slow or hanging due to a different reason. It is also difficult to establish the cause of the deadlock. In general, developers deal with deadlocks by using analysis tools, introducing application-specific deadlock detection mechanisms, or simply by using techniques to avoid the occurrence of deadlocks by construction. In this paper we propose a different approach. We believe that if deadlocks manifest at runtime, as exceptions, programmers will be able to identify these deadlocks in an accurate and timely manner. We leverage two insights to make this practical: (i) most deadlocks occurring in real systems involve only two threads acquiring two locks (TTTL deadlocks); and (ii) it’s possible to detect TTTL deadlocks efficiently enough for most practical systems. We conducted a study on bug reports and found that more than 90% of identified deadlocks were indeed TTTL.We extended Java’s ReentrantLock class to detect TTTL deadlocks and measured the performance overhead of this approach with a conservative benchmark. For applications whose execution time is not dominated by locking, the overhead is estimated as below 6%. Empirical usability evaluation in two experiments showed that students finished tasks 16.87% to 30.7% faster on the average using our approach with the lock being the most significant factor behind it, and, in one of the experiments they were able to identify the defects more accurately with a signficant 81.25% increase in the number of correct answers when deadlock exceptions where present. / Deadlocks são um tipo comum de bug de concorrência. Quando um deadlock acontece, é difícil determinar claramente se houve um deadlock de verdade ou se a aplicação está lenta ou travada por qualquer outro motivo. Também é difícil estabelecer a causa do deadlock. Em geral, desenvolvedores lidam com deadlocks de várias maneiras: utilizando ferramentas analíticas; utilizando mecanismos especificos da aplicação para detectar deadlocks; ou simplesmente usando técnicas para evitar a ocorrência de deadlocks no momento da construção do código. Neste trabalho, propomos uma abordagem diferente. Acreditamos que se deadlocks se manifestarem durante a execução na forma de exceções, programadores serão capazes de identificar esses deadlocks de forma mais precisa e mais rápida. Levamos em consideração alguns aspectos para tornar esta abordagem prática: (i) a maioria dos deadlocks que ocorrem em sistemas reais envolvem apenas duas threads adquirindo dois locks ou two-thread, two-lock (TTTL) deadlock; e (ii) é possível detectar TTTL deadlocks de forma suficientemente eficiente para uso prático na maioria dos sistemas. Conduzimos um estudo com bugs reportados em sistemas de software de larga escala e descobrimos que mais de 90% dos bugs identificados como deadlocks eram de fato TTTL. Extendemos a classe ReentrantLock de Java para detectar TTTL deadlocks e medimos seu overhead na performance com um benchmark bastante conservador onde medimos o overhead das operações de trava quando deadlocks não são possíveis. Para aplicações cujo tempo de execução não é dominado por travas, o impacto médio no tempo de execução é na ordem de 6%. Realizamos uma avaliação empírica para testar usabilidade através de dois experimentos. Nesta avaliação, mostramos que, em média, estudantes terminam tarefas de 16.87% a 30.7% mais rapidamente usando nossa abordagem, sendo o tipo de abordagem o fator de maior significância e, em um dos experimentos, estudantes foram capazes de identificar mais corretamente a causa dos bugs, mostrando que o número de respostas corretas aumentou significativamente em 81.25% quando as exceções propostas estavam presentes.

This thesis proposes a synthesis methodology which is capable of fault-tolerance and deadlock-free for constructing a custom NoC topology in 3D ICs. In this thesis, the processors and their communications can be synthesized simultaneously in the system-level floorplanning with fault tolerant consideration, called 3D-NoC-FT. Experimental results show that the pro-posed 3D-NoC-FT produces custom 3D NoCs with lower power dissipation than previous works. This method is also more scalable, which makes it ideal for complicated 3D NoC de-signs. Compared with the previous 3D NoC work (3D-SAL-FP) without link fault tolerance, our fault tolerant method outperforms on the average the power dissipation by 1.67X with rela-tively small overhead of latency by 17% and the number of TSV by 35%, respectively.

Minority government is defined by the relationship between the legislative and executive branches of government in parliamentary democracies; it means single-party cabinet or coalition cabinet, which are not supported by a parliamentary majority in Parliamentary and Semi-Presidential countries. For instance, in Taiwan, Chen Shui-bian won the Presidential Election in 2000, but he just garnered 39.3¢Mof the popular vote, so he was a minority president. After election, the president Chen Shui-bian appointed Chang Chun-hsiung as Premier (Executive Yuan); therefore, ¡§Chen Shui-bian government¡¨ indeed was a minority government. Because the ¡§regime turnover¡¨ happened in Taiwan is the first time, as a ruling party, Democratic Progressive Party (DPP) didn¡¦t deal with very well in cabinet portfolios, policy concession or policy implementation. On the other hand, the political disturbance has been existed in the executive-legislative relations since 2000. Under this context, to understand why minority governments form and how they operate become an important issue. As we noted, there is not rich literature on minority governments, so this is why the study focus on initially exploring minority government. This essay includes two research subjects: The first point is to analyze theory of minority government. By following the documents of the scholars¡¦ comparison and research, I try to explain why a minority government form from the part of the institution and strategy; I also introduce the operation and performance of minority government briefly. The second point is to do the studies of cases of minority government and performance in Norway and Fourth Republic France: From the two empirical cases, I expect to find a suitable solution for the constitutional deadlock at present in Taiwan.

Many signal and image processing systems for high-throughput, high-performance applications require concurrent implementations in order to realize desired performance. Developing software for concurrent systems is widely acknowledged to be difficult, with common industry practice leaving the burden of preventing concurrency problems on the programmer. The Kahn Process Network model provides the mathematically provable property of determinism of a program result regardless of the execution order of its processes, including concurrent execution. This model is also natural for describing streams of data samples in a signal processing system, where processes transform streams from one data type to another. However, a Kahn Process Network may require infinite memory to execute. I present the dynamic distributed deadlock detection and resolution (D4R) algorithm, which permits execution of Process Networks in bounded memory if it is possible. It detects local deadlocks in a Process Network, determines whether the deadlock can be resolved and, if so, identifies the process that must take action to resolve the deadlock. I propose the Computational Process Network (CPN) model which is based on the formalisms of Kahn’s PN model, but with enhancements that are designed to make it efficiently implementable. These enhancements include multi-token transactions to reduce execution overhead, multi-channel queues for multi-dimensional synchronous data, zero-copy semantics, and consumer and producer firing thresholds for queues. Firing thresholds enable memoryless computation of sliding window algorithms, which are common in signal processing systems. I show that the Computational Process Network model preserves the formal properties of Process Networks, while reducing the operations required to implement sliding window algorithms on continuous streams of data. I also present a high-throughput software framework that implements the Computational Process Network model using C++, and which maps naturally onto distributed targets. This framework uses POSIX threads, and can exploit parallelism in both multi-core and distributed systems. Finally, I present case studies to exercise this framework and demonstrate its performance and utility. The final case study is a three-dimensional circular convolution sonar beamformer and replica correlator, which demonstrates the high throughput and scalability of a real-time signal processing algorithm using the CPN model and framework. / text

Deadlocks are critical events in Flexible Manufacturing Cells (FMC) that result from circular waits among a set of resources. Circular waits happen when a set of resources with finite capacity are in a permanent hold due to wait state to admit new jobs. Past literature examines the deadlock-free scheduling in FMCs considering many types of resources and techniques. This thesis proposes a new resource-oriented deadlock-free approach using a robot equipped with dual-grippers serving as a material handler in a FMC. The proposed methodology uses Constraint Programming (CP). The system performance is analyzed using different buffer configurations. Many test problems are generated to validate the developed models. The finding demonstrates that the proposed dual-gripper robot (DGR) can outperform the single-gripper robot (SGR) in many settings for FMCs. Likewise, the experience with the CP for the modeling and solving approach proposed in this research consolidates its application to FMC deadlock-free scheduling problems.

Deadlocks are critical events in Flexible Manufacturing Cells (FMC) that result from circular waits among a set of resources. Circular waits happen when a set of resources with finite capacity are in a permanent hold due to wait state to admit new jobs. Past literature examines the deadlock-free scheduling in FMCs considering many types of resources and techniques. This thesis proposes a new resource-oriented deadlock-free approach using a robot equipped with dual-grippers serving as a material handler in a FMC. The proposed methodology uses Constraint Programming (CP). The system performance is analyzed using different buffer configurations. Many test problems are generated to validate the developed models. The finding demonstrates that the proposed dual-gripper robot (DGR) can outperform the single-gripper robot (SGR) in many settings for FMCs. Likewise, the experience with the CP for the modeling and solving approach proposed in this research consolidates its application to FMC deadlock-free scheduling problems.

No description available.

No description available.