Dissertationen zum Thema „Multithreaded application“

Multithreading is today a very common technology to achieve concurrency within software. Today there exists three commonly used threading strategies for multithreaded application servers. These are thread per client, thread per request and thread pool. Earlier studies has shown that the choice of threading strategy is not that important. Our measurements show that the choice of threading architecture becomes more important when the application comes under high load. We will in this study present a throttling concept which can give thread per client almost as good qualities as the thread pool strategy when it comes to performance. No architecture change is required. This concept has been evaluated on three types of hardware, ranging from 1 to 64 CPUs, using 6 alternatives loads and both in C and Java. We have also identified that there is a high correlation between average response times and the length of the run time queue. This can be used to construct a self tuning throttling algorithm that makes the introduction of the throttle concept even simpler, since it does require any configuring.

El disseny del llenguatge Java, que inclou aspectes importants com són la seva portabilitat i neutralitat envers l'arquitectura, les seves capacitats multithreading, la seva familiaritat (degut a la seva semblança amb C/C++), la seva robustesa, les seves capacitats en seguretat i la seva naturalesa distribuïda, fan que sigui un llenguatge potencialment interessant per ser utilitzat en entorns paral·lels com són els entorns de computació d'altes prestacions (HPC), on les aplicacions poden treure profit del suport que ofereix Java a l'execució multithreaded per realitzar càlculs en paral·lel, o en entorns e-business, on els servidors Java multithreaded (que segueixen l'especificació J2EE) poden treure profit de les capacitats multithreading de Java per atendre de manera concurrent un gran nombre de peticions.<br/><br/>No obstant, l'ús de Java per la programació paral·lela ha d'enfrontar-se a una sèrie de problemes que fàcilment poden neutralitzar el guany obtingut amb l'execució en paral·lel. El primer problema és el gran overhead provocat pel suport de threads de la JVM quan s'utilitzen threads per executar feina de gra fi, quan es crea un gran nombre de threads per suportar l'execució d'una aplicació o quan els threads interaccionen estretament mitjançant mecanismes de sincronització. El segon problema és la degradació en el rendiment produïda quan aquestes aplicacions multithreaded s'executen en sistemes paral·lels multiprogramats. La principal causa d'aquest problemes és la manca de comunicació entre l'entorn d'execució i les aplicacions, la qual pot induir a les aplicacions a fer un ús descoordinat dels recursos disponibles.<br/><br/>Aquesta tesi contribueix amb la definició d'un entorn per analitzar i comprendre el comportament de les aplicacions Java multithreaded. La contribució principal d'aquest entorn és que la informació de tots els nivells involucrats en l'execució (aplicació, servidor d'aplicacions, JVM i sistema operatiu) està correlada. Aquest fet és molt important per entendre com aquest tipus d'aplicacions es comporten quan s'executen en entorns que inclouen servidors i màquines virtuals, donat que l'origen dels problemes de rendiment es pot trobar en qualsevol d'aquests nivells o en la seva interacció.<br/><br/>Addicionalment, i basat en el coneixement adquirit mitjançant l'entorn d'anàlisis proposat, aquesta tesi contribueix amb mecanismes i polítiques de planificació orientats cap a l'execució eficient d'aplicacions Java multithreaded en sistemes multiprocessador considerant les interaccions i la coordinació dels mecanismes i les polítiques de planificació en els diferents nivells involucrats en l'execució. La idea bàsica consisteix en permetre la cooperació entre les aplicacions i l'entorn d'execució en la gestió de recursos establint una comunicació bi-direccional entre les aplicacions i el sistema. Per una banda, les aplicacions demanen a l'entorn d'execució la quantitat de recursos que necessiten. Per altra banda, l'entorn d'execució pot ser inquirit en qualsevol moment per les aplicacions ser informades sobre la seva assignació de recursos. <br/><br/>Aquesta tesi proposa que les aplicacions utilitzin la informació proporcionada per l'entorn d'execució per adaptar el seu comportament a la quantitat de recursos que tenen assignats (aplicacions auto-adaptables). Aquesta adaptació s'assoleix en aquesta tesi per entorns HPC per mitjà de la mal·leabilitat de les aplicacions, i per entorns e-business amb una proposta de control de congestió que fa control d'admissió basat en la diferenciació de connexions SSL per prevenir la degradació del rendiment i mantenir la Qualitat de Servei (QoS).<br/><br/>Els resultats de l'avaluació demostren que subministrar recursos de manera dinàmica a les aplicacions auto-adaptables en funció de la seva demanda millora el rendiment de les aplicacions Java multithreaded tant en entorns HPC com en entorns e-business. Mentre disposar d'aplicacions auto-adaptables evita la degradació del rendiment, el subministrament dinàmic de recursos permet satisfer els requeriments de les aplicacions en funció de la seva demanda i adaptar-se a la variabilitat de les seves necessitats de recursos. D'aquesta manera s'aconsegueix una millor utilització dels recursos donat que els recursos que no utilitza una aplicació determinada poden ser distribuïts entre les altres aplicacions.<br>The design of the Java language, which includes important aspects such as its portability and architecture neutrality, its multithreading facilities, its familiarity (due to its resemblance with C/C++), its robustness, its security capabilities and its distributed nature, makes it a potentially interesting language to be used in parallel environments such as high performance computing (HPC) environments, where applications can benefit from the Java multithreading support for performing parallel calculations, or e-business environments, where multithreaded Java application servers (i.e. following the J2EE specification) can take profit of Java multithreading facilities to handle concurrently a large number of requests.<br/><br/>However, the use of Java for parallel programming has to face a number of problems that can easily offset the gain due to parallel execution. The first problem is the large overhead incurred by the threading support available in the JVM when threads are used to execute fine-grained work, when a large number of threads are created to support the execution of the application or when threads closely interact through synchronization mechanisms. The second problem is the performance degradation occurred when these multithreaded applications are executed in multiprogrammed parallel systems. The main issue that causes these problems is the lack of communication between the execution environment and the applications, which can cause these applications to make an uncoordinated use of the available resources.<br/><br/>This thesis contributes with the definition of an environment to analyze and understand the behavior of multithreaded Java applications. The main contribution of this environment is that all levels in the execution (application, application server, JVM and operating system) are correlated. This is very important to understand how this kind of applications behaves when executed on environments that include servers and virtual machines, because the origin of performance problems can reside in any of these levels or in their interaction.<br/><br/>In addition, and based on the understanding gathered using the proposed analysis environment, this thesis contributes with scheduling mechanisms and policies oriented towards the efficient execution of multithreaded Java applications on multiprocessor systems considering the interactions and coordination between scheduling mechanisms and policies at the different levels involved in the execution. The basis idea consists of allowing the cooperation between the applications and the execution environment in the resource management by establishing a bi-directional communication path between the applications and the underlying system. On one side, the applications request to the execution environment the amount of resources they need. On the other side, the execution environment can be requested at any time by the applications to inform them about their resource assignments. <br/><br/>This thesis proposes that applications use the information provided by the execution environment to adapt their behavior to the amount of resources allocated to them (self-adaptive applications). This adaptation is accomplished in this thesis for HPC environments through the malleability of the applications, and for e-business environments with an overload control approach that performs admission control based on SSL connections differentiation for preventing throughput degradation and maintaining Quality of Service (QoS).<br/><br/>The evaluation results demonstrate that providing resources dynamically to self-adaptive applications on demand improves the performance of multithreaded Java applications as in HPC environments as in e-business environments. While having self-adaptive applications avoids performance degradation, dynamic provision of resources allows meeting the requirements of the applications on demand and adapting to their changing resource needs. In this way, better resource utilization is achieved because the resources not used by some application may be distributed among other applications.

Anisotropic mesh adaptation is a powerful way to directly minimise the computational cost of mesh based simulation. It is particularly important for multi-scale problems where the required number of floating-point operations can be reduced by orders of magnitude relative to more traditional static mesh approaches. Increasingly, finite element/volume codes are being optimised for modern multicore architectures. Inter-node parallelism for mesh adaptivity has been successfully implemented by a number of groups using domain decomposition methods. However, thread-level parallelism using programming models such as OpenMP is significantly more challenging because the underlying data structures are extensively modified during mesh adaptation and a greater degree of parallelism must be realised while keeping the code race-free. In this thesis we describe a new thread-parallel implementation of four anisotropic mesh adaptation algorithms, namely edge coarsening, element refinement, edge swapping and vertex smoothing. For each of the mesh optimisation phases we describe how safe parallel execution is guaranteed by processing workitems in batches of independent sets and using a deferred-operations strategy to update the mesh data structures in parallel without data contention. Scalable execution is further assisted by creating worklists using atomic operations, which provides a synchronisation-free alternative to reduction-based worklist algorithms. Additionally, we compare graph colouring methods for the creation of independent sets and present an improved version which can run up to 50% faster than existing techniques. Finally, we describe some early work on an interrupt-driven work-sharing for-loop scheduler which is shown to perform better than existing work-stealing schedulers. Combining all aforementioned novel techniques, which are generally applicable to other unordered irregular problems, we show that despite the complex nature of mesh adaptation and inherent load imbalances, we achieve a parallel efficiency of 60% on an 8-core Intel(R) Xeon(R) Sandy Bridge and 40% using 16 cores on a dual-socket Intel(R) Xeon(R) Sandy Bridge ccNUMA system.

<p>Routers are probably the most important component of a NoC, as the performance of the whole network is driven by the routers’ performance. Cost for the whole network in terms of area will also be minimised if the router design is kept small. A new application specific processor architecture for implementing NoC routers is proposed in this master thesis, which will be called µNP (Micro-Network Processor). The aim is to offer a solution in which there is a trade-off between the high performance of routers implemented in hardware and the high level of flexibility that could be achieved by loading a software that routed packets into a GPP. Therefore, a study including the design of a hardware based router and a GPP based router has been conducted. In this project the first version of the µNP has been designed and a complete instruction set, along with some sample programs, is also proposed. The results show that, in the best case for all implementation options, µNP was 7.5 times slower than the hardware based router. It has also behaved more than 100 times faster than the GPP based router, keeping almost the same degree of flexibility for routing purposes within NoC.</p>

Faults are common-place and inevitable in complex applications. Hence, automated techniques are necessary to analyze failed executions and debug the application to locate the fault. For locating faults in programs, dynamic slices have been shown to be very effective in reducing the effort of debugging. The user needs to inspect only a small subset of program statements to get to the root cause of the fault. While prior work has primarily focussed on single-threaded programs, this dissertation shows how dynamic slicing can be used for fault location in multithreaded programs. This dissertation also shows that dynamic slices can be used to track down faults due to data races in multithreaded programs by incorporating additional data dependences that arise in the presence of many threads. In order to construct the dynamic slices, dependence traces are collected and processed. However, program runs generate traces in the order of Gigabytes in a few seconds. Hence, for multithreaded program runs that are long-running, the process of collecting and storing these traces poses a significant challenge. This dissertation proposes two techniques to overcome this challenge. Experiments indicate that the techniques combined can reduce the size of the traces by 3 orders of magnitude. For applications that are critical and for which down time is highly detrimental, techniques for surviving software failures and letting the execution continue are desired. This dissertation proposes one such technique to recover applications from a class of faults that are caused by the execution environment and prevent the fault in future runs. This technique has been successfully used to avoid faults in a variety of applications caused due to thread scheduling, heap overflow, and malformed user requests. Case studies indicate that, for most environment bugs, the point in the execution where the environment modification is necessary can be clearly pin-pointed by using the proposed system and the fault can be avoided in the first attempt. The case studies also show that the patches needed to prevent the different faults are simple and the overhead induced by the system during the normal run of the application is less than 10 \%, on average.

Embedded systems are getting more complex and require more intensive processing capabilities. They must be able to adapt to the rapid evolution of the high-end embedded applications that are characterized by their high computation-intensive workloads (order of TOPS: Tera Operations Per Second), and their high level of parallelism. Moreover, since the dynamism of the applications is becoming more significant, powerful computing solutions should be designed accordingly. By exploiting efficiently the dynamism, the load will be balanced between the computing resources, which will improve greatly the overall performance. To tackle the challenges of these future high-end massively-parallel dynamic embedded applications, we have designed the AHDAM architecture, which stands for "Asymmetric Homogeneous with Dynamic Allocator Manycore architecture". Its architecture permits to process applications with large data sets by efficiently hiding the processors' stall time using multithreaded processors. Besides, it exploits the parallelism of the applications at multiple levels so that they would be accelerated efficiently on dedicated resources, hence improving efficiently the overall performance. AHDAM architecture tackles the dynamism of these applications by dynamically balancing the load between its computing resources using a central controller to increase their utilization rate.The AHDAM architecture has been evaluated using a relevant embedded application from the telecommunication domain called "spectrum radio-sensing". With 136 cores running at 500 MHz, AHDAM architecture reaches a peak performance of 196 GOPS and meets the computation requirements of the application.

The scalability of parallel applications executing on multithreaded and multicore multiprocessors is often quite limited due to large degrees of contention over shared resources on these systems. In fact, negative scalability frequently occurs such that a non-negligable performance loss is observed through the use of more processors and cores. In this dissertation, we present a prediction model for identifying efficient operating points of concurrency in multithreaded scientific applications in terms of both performance as a primary objective and power secondarily. We also present a runtime system that uses live analysis of hardware event rates through the prediction model to optimize applications dynamically. We discuss a dynamic, phase-aware performance prediction model (DPAPP), which combines statistical learning techniques, including multivariate linear regression and artificial neural networks, with runtime analysis of data collected from hardware event counters to locate optimal operating points of concurrency. We find that the scalability model achieves accuracy approaching 95%, sufficiently accurate to identify improved concurrency levels and thread placements from within real parallel scientific applications. Using DPAPP, we develop a prediction-driven runtime optimization scheme, called ACTOR, which throttles concurrency so that power consumption can be reduced and performance can be set at the knee of the scalability curve of each parallel execution phase in an application. ACTOR successfully identifies and exploits program phases where limited scalability results in a performance loss through the use of more processing elements, providing simultaneous reductions in execution time by 5%-18% and power consumption by 0%-11% across a variety of parallel applications and architectures. Further, we extend DPAPP and ACTOR to include support for runtime adaptation of DVFS, allowing for the synergistic exploitation of concurrency throttling and DVFS from within a single, autonomically-acting library, providing improved energy-efficiency compared to either approach in isolation.<br>Ph. D.

The goal of this thesis is to experiment with the latest web technologies and to design new process for mobile application creation. It is possible to create multiplatform applications which are almost unrecognizable from native applications by proposed procedures.  It is focused on performance and native behaviour of the user interface in this thesis. Described practices are demonstrated on application designed for work with historical maps, which is able to show maps from historical archives whole over world real-time. Rapid acceleration has been showed on the demonstrative application compared to standard process of creation of web applications.

The number of transistors on an integrated circuit keeps doubling every two years. This increasing number of transistors is used to integrate more processing cores on the same chip. However, due to power density and ILP diminishing returns, the single-thread performance of such processing cores does not double every two years, but doubles every three years and a half. Computer architecture research is mainly driven by simulation. In computer architecture simulators, the complexity of the simulated machine increases with the number of available transistors. The more transistors, the more cores, the more complex is the model. However, the performance of computer architecture simulators depends on the single-thread performance of the host machine and, as we mentioned before, this is not doubling every two years but every three years and a half. This increasing difference between the complexity of the simulated machine and simulation speed is what we call the simulation speed gap. Because of the simulation speed gap, computer architecture simulators are increasingly slow. The simulation of a reference benchmark may take several weeks or even months. Researchers are concious of this problem and have been proposing techniques to reduce simulation time. These techniques include the use of reduced application input sets, sampled simulation and parallelization. Another technique to reduce simulation time is raising the level of abstraction of the simulated model. In this thesis we advocate for this approach. First, we decide to use trace-driven simulation because it does not require to provide functional simulation, and thus, allows to raise the level of abstraction beyond the instruction-stream representation. However, trace-driven simulation has several limitations, the most important being the inability to reproduce the dynamic behavior of multithreaded applications. In this thesis we propose a simulation methodology that employs a trace-driven simulator together with a runtime sytem that allows the proper simulation of multithreaded applications by reproducing the timing-dependent dynamic behavior at simulation time. Having this methodology, we evaluate the use of multiple levels of abstraction to reduce simulation time, from a high-speed application-level simulation mode to a detailed instruction-level mode. We provide a comprehensive evaluation of the impact in accuracy and simulation speed of these abstraction levels and also show their applicability and usefulness depending on the target evaluations. We also compare these levels of abstraction with the existing ones in popular computer architecture simulators. Also, we validate the highest abstraction level against a real machine. One of the interesting levels of abstraction for the simulation of multi-cores is the memory mode. This simulation mode is able to model the performanceof a superscalar out-of-order core using memory-access traces. At this level of abstraction, previous works have used filtered traces that do not include L1 hits, and allow to simulate only L2 misses for single-core simulations. However, simulating multithreaded applications using filtered traces as in previous works has inherent inaccuracies. We propose a technique to reduce such inaccuracies and evaluate the speed-up, applicability, and usefulness of memory-level simulation. All in all, this thesis contributes to knowledge with techniques for the simulation of chip multiprocessors with hundreds of cores using traces. It states and evaluates the trade-offs of using varying degress of abstraction in terms of accuracy and simulation speed.

Network on Chip (NoC) architectures provide scalable platforms for designing Systems on Chip (SoC) with large number of cores. Developing products and applications using an NoC architecture offers many challenges and opportunities. A tool which can map an application or a set of applications to a given NoC architecture will be essential. In this thesis we first survey current techniques and we present our proposals for mapping and scheduling of concurrent applications to NoCs with multithreaded processors as computational resources. NoC platforms are basically a special class of Multiprocessor Embedded Systems (MPES). Conventional MPES architectures are mostly bus-based and, thus, are exposed to potential difficulties regarding scalability and reusability. There has been a lot of research on MPES development including work on mapping and scheduling of applications. Many of these results can also be applied to NoC platforms. Mapping and scheduling are known to be computationally hard problems. A large range of exact and approximate optimization algorithms have been proposed for solving these problems. The methods include Branch-and–Bound (BB), constructive and transformative heuristics such as List Scheduling (LS), Genetic Algorithms (GA) and various types of Mathematical Programming algorithms. Concurrent applications are able to capture a typical embedded system which is multifunctional. Concurrent applications can be executed on an NoC which provides a large computational power with multiple on-chip computational resources. Improving the time performances of concurrent applications which are running on Network on Chip (NoC) architectures is mainly correlated with the ability of mapping and scheduling methodologies to exploit the Thread Level Parallelism (TLP) of concurrent applications through the available NoC parallelism. Matching the architectural parallelism to the application concurrency for obtaining good performance-cost tradeoffs is  another aspect of the problem. Multithreading is a technique for hiding long latencies of memory accesses, through the overlapped execution of several threads. Recently, Multi-Threaded Processors (MTPs) have been designed providing the architectural infrastructure to concurrently execute multiple threads at hardware level which, usually, results in a very low context switching overhead. Simultaneous Multi-Threaded Processors (SMTPs) are superscalar processor architectures which adaptively exploit the coarse grain and the fine grain parallelism of applications, by simultaneously executing instructions from several thread contexts. In this thesis we make a case for using SMTPs and MTPs as NoC resources and show that such a multiprocessor architecture provides better time performances than an NoC with solely General-purpose Processors (GP). We have developed a methodology for task mapping and scheduling to an NoC with mixed SMTP, MTP and GP resources, which aims to maximize the time performance of concurrent applications and to satisfy their soft deadlines. The developed methodology was evaluated on many configurations of NoC-based platforms with SMTP, MTP and GP resources. The experimental results demonstrate that the use of SMTPs and MTPs in NoC platforms can significantly speed-up applications.

With computer systems increasingly relying on multithreading for increasing performance the importance of multithreaded programs also increase. In this comparative study of performance and implementation complexity, the same multithreaded key-value store database was developed in three languages: Java, Rust and C++. By using a read-focused and a write-focused test, the performance of the three implementations were compared. The amount of operations and cores was varied between the tests. The implementation complexity of the programs was compared by the number of lines of codes (LOC). The results showed that Java was measurably slower at all tests while Rust and C++ displayed roughly equal performance. However, C++ required significantly more lines of code than Rust and Java. This led to the conclusion that in the case of implementing a multithreaded key-value store, Rust is the best suited language.<br>I och med att datasystem i allt större omfattning förlitar sig på multitrådning för att förbättra sin prestandan ökar också vikten av flertrådiga program. I denna jämförande studie av prestanda och implementationskomplexitet, utvecklades samma flertrådade key-value store databas i tre programspråk: Java, Rust och C++. Genom användning av ett läs-fokuserat och ett skriv-fokuserat test jämfördes prestandan hos de tre implementationerna. Antalet operationer och kärnor varierades mellan testerna. Implementationskomplexiteten jämfördes genom att jämföra antalet kodrader (LOC). Resultaten visade att Java var mätbart långsammare vid samtliga tester medan Rust och C++ hade likvärdig prestanda. Däremot krävde C++ betydligt fler rader kod än Rust och Java. Av detta drogs slutsatsen att för att utveckla en flertrådad key-value store databas var Rust det bäst lämpade språket.

The diploma thesis deals with the design and implementation of the system that will control the water supply for the family house and its garden. The system aslo allows you to store a history that can be viewed via the web interface. The web interface also allows you to set system parameters and monitor the current status.

This thesis discusses techniques for improving the fault tolerance of multithreaded applications. We consider the impact on fault tolerance methods of sharing address space and resources. We develop techniques in two broad categories: conservative multithreaded fault-tolerance (C-MTFT), which recovers an entire application on the failure of a single thread, and optimistic multithreaded fault-tolerance (OMTFT), which recovers threads independently as necessary. In the latter category, we provide a novel approach to recover hung threads while improving recovery time by managing access to shared resources so that hung threads can be restarted while other threads continue execution.<br>text

碩士<br>國立交通大學<br>電子工程系所<br>96<br>Due to task divergence in most embedded systems, heterogeneous dual-core/multi-core SoC, i.e. RISC+DSP, is accepted as a cost-effective solution for the increasing computation demands in mobile media applications. TI Davinci, for example, is one popular dual-core platform, where the DSP, as the slave or coprocessor, performs the computation-intensive task sent and requested by the host processor (i.e. RISC). However, inefficient DSP-task management, such as task scheduling and task dispatch, induces inter-processor communication (IPC) overheads and thus lowers the DSP performance. In order to improve DSP performance, a multithreaded DSP coprocessor for multimedia applications is proposed in this thesis. The DSP coprocessor consists of a smart coprocessor interface (SCI) and an application-specific interleaved multithreaded datapath. The proposed SCI can dynamically manage DSP-tasks and effectively reduce IPC overheads, while the interleaved multithreaded datapath can exploit thread-level parallelism (TLP) to tolerate full pipeline latency. A dual-core SystemC transaction-level virtual platform, constructed by CoWare electronic system level (ESL) design platform, is used to evaluate the DSP performance affected by the SCI. To encode a 256x256 JPEG image, the SCI reduces 68% and 15% total execution time comparing that with task management on MPU supported by OS and on DSP supported by a μ-kernel or RTOS, respectively. On the other hand, a cascaded adder, multiplier, accumulator, and shifter (A-M-A-S) functional units are applied on the proposed DSP datapath. This composite datapath is able to perform complicated operations, such as addition-multiplication (AM), multiplication-accumulation (MA), and addition-multiplication-accumulation-shift (AMAS) for multimedia applications. The proposed multithreaded DSP coprocessor is implemented by TSMC 0.13μm CMOS technology. The implementation results show that it can operate at 250MHz with 40mW power consumption. The chip area is 2.7x 2.7mm2 and the SCI occupies only 0.65% of the total chip size

When parallel applications do not fully utilize the cores that are available to them they are missing the opportunity to have better performance. Sometimes threads have to wait for other threads. I call the code segments that make other threads wait bottlenecks. Examples of these bottlenecks include contended critical sections, threads arriving late to barriers and the slowest stage of a pipelined program. Other times all threads are running but some of them, which I call lagging threads, are making less progress, setting the stage to become bottlenecks. My thesis proposes identifying the code segments that are more critical for performance and efficiently accelerating them using faster cores, by either migrating execution to large cores of an Asymmetric Chip Multi-Processor (ACMP) or executing locally on DVFS-accelerated cores. The key contribution of this dissertation is a Utility of Acceleration metric that combines a measure of the acceleration for each code segment with a measure of its criticality. This metric enables meaningful comparisons to decide which bottlenecks or lagging threads to accelerate with each of the available acceleration mechanisms. My evaluation shows significant performance improvement for single multithreaded applications and sets of multiple single- and multi-threaded applications, and also reduction in energy-delay product due to the efficient utilization of the available acceleration mechanisms.<br>text

碩士<br>國立清華大學<br>資訊工程學系<br>87<br>Performance evalution is one of the improtant courses in the world of computer science. Many researches have proposed various kinds of methods to analyze the program behavior. Among them, program tracing and performance monitoring softwares have been used widely to study the execution characteristics of programs. But in the Windows/x86 platform, it is very difficult to build such a software tool due to the facts that the Windows operating systems and many applications running on top of it are distributed without source code and the x86 CPU has a complicated instruction set architecture. In this thesis, we propose a method to build a program tracing tool in the Windows NT/x86 platfrom, which aims at tracing the multi-threaded Windows applications without source code available. We have applied our tracing system to some benchmark programs, and results of analyzing the characteristics of these programs are presented.

abstract: Debugging is a hard task. Debugging multi-threaded applications with their inherit non-determinism is all the more difficult. Non-determinism of any kind adds to the difficulty of cyclic debugging. In Android applications which are written in Java, threads and concurrency constructs introduce non-determinism to the program execution. Even with the same input, consecutive runs may not be the same and reproducing the same bug is a challenging task. This makes it difficult to understand and analyze the execution behavior or to understand the source of a failing execution. This thesis introduces a replay mechanism for Android applications written in Java and is based on the Lamport Clock. This tool provides the user with a controlled debugging environment, where the program execution follows the identical partially ordered happened-before dependency among threads, as during the recorded execution. In this, certain significant events like thread creation, synchronization etc. are recorded during run-time. They can later be replayed off-line, as many times as needed to pinpoint and fix an error in the application. It is software based approach and has been implemented by modifying the Dalvik Virtual Machine in the Android platform. The method of replay described in this thesis is independent of the underlying operating system scheduler.<br>Dissertation/Thesis<br>M.S. Computer Science 2011

博士<br>國立交通大學<br>資訊科學與工程研究所<br>95<br>Networking applications today demand a hardware platform with stronger computational or memory access capabilities as well as the ability to efficiently adapt to changes of protocols or product specifications. Being the ordinary options, however, neither a general purpose processor architecture, which is usually slowed down by kernel-user space communications and context switches, nor an ASIC, which lacks the flexibility and requires much development period, measures up. In this thesis, we discuss (1) the feasibility of applying the emerging alternative, network processors featuring the multithreaded multiprocessor architecture, rich resources, minor context switch overhead, and flexibility, to solve the problem, and (2) the ways of exploiting those resources when dealing with applications of different computational and memory access requirements. We start by surveying network processors which are then categorized into two types, the coprocessors-centric and the core-centric ones. For the former, the coprocessors take care of the data plane manipulation whose load is usually much heavier than the one of the control plane, while in the latter the core processor handles the most part of packet processing, including the control plane and data plane. After that we evaluate real implementations of computational intensive and memory access intensive applications over the coprocessors-centric and core-centric platforms, respectively, aiming to unveil the bottlenecks of the implementations as well as the allocation measures. Finally, based on the evaluations, analytical models are formalized and simulation environments are built to observe possible design implications for these two types of network processors.

碩士<br>高苑科技大學<br>機械與自動化工程研究所<br>96<br>The main purpose of this paper is to promote the efficiency of a control system by using a multithread digital control design. In this system, the management of a computer’s input and output information is handled appropriately by the program language to promote the efficiency when the computer is applied to treat all the information. The advantage of this multithread digital control design is to activate each procedure running simultaneously and reduce the process when using single-thread to execute events and wait in line. In this paper , case studies of multithread application used in image tracking and robot control are introduced. The multithread digital control design is used in the robotic arm’s tracking system of image capture and control output . To compare the multithread system with the single-thread system, the results reveal that the speed of the tracking system can be improved by using the multithread technique under an immediate procedure plan. Especially when the image tracing feedback is under control, there will be lots of data under process. That will be more necessary to apply this method in order to improve the system speed and accomplish the goal of this study, purpose that to reach the study.

Communicating Sequential Processes (CSP) is a formal language whose primary purpose is to model and verify concurrent systems. The CSP++ toolset was created to embody the concept of selective formalism by making machine-readable CSPm specifications both executable (through the automatic synthesis of C++ source) and extensible (by allowing the integration of C++ user-coded functions). However, these user-coded functions were limited by their inability to share data with each other, which meant that their application was constrained to solving simple problems in isolation. We extend CSP++ by providing user-coded functions in the same CSP process with safe access to a shared storage area, similar in concept and API to Pthreads' thread-local storage, enabling cooperation between them and granting them the ability to undertake more complex tasks without breaking the formalism of the underlying specification. This feature's utility is demonstrated in our line-following robot case study.