Thesis (Ph.D)--Electrical and Computer Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Paul Hasler; Committee Co-Chair: David V. Anderson. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Thesis (M.S.)--Oregon State University, 2008. / Printout. Includes bibliographical references (leaves 57-59). Also available on the World Wide Web.

Software components expose Application Programming Interfaces (APIs) as a means to access their functionality, and facilitate reuse. Developers use APIs supplied by programming languages to access the core data structures and algorithms that are part of the language framework. They use the APIs of third-party libraries for specialized tasks. Thus, APIs play a central role in mediating a developer's interaction with software, and the interaction between different software components. However, APIs are often large, complex and hard to navigate. They may have hundreds of classes and methods, with incomplete or obsolete documentation. They may encapsulate concurrency behaviour that the developer is unaware of. Finding the right functionality in a large API, using APIs correctly, and maintaining software that uses a constantly evolving API are challenges that every developer runs into. In this thesis, we design automated techniques to address two problems pertaining to APIs (1) Concurrency analysis of APIs, and (2) API mining. Speci cally, we consider the concurrency analysis of asynchronous APIs, and mining of math APIs to infer the functional behaviour of API methods. The problem of concurrency bugs such as race conditions and deadlocks has been well studied for multi-threaded programs. However, developers have been eschewing a pure multi-threaded programming model in favour of asynchronous programming models supported by asynchronous APIs. Asynchronous programs and multi-threaded programs have different semantics, due to which existing techniques to analyze the latter cannot detect bugs present in programs that use asynchronous APIs. This thesis addresses the problem of concurrency analysis of programs that use asynchronous APIs in an end-to-end fashion. We give operational semantics for important classes of asynchronous and event-driven systems. The semantics are designed by carefully studying real software and serve to clarify subtleties in scheduling. We use the semantics to inform the design of novel algorithms to find races and deadlocks. We implement the algorithms in tools, and show their effectiveness by finding serious bugs in popular open-source software. To begin with, we consider APIs for asynchronous event-driven systems supporting pro-grammatic event loops. Here, event handlers can spin event loops programmatically in addition to the runtime's default event loop. This concurrency idiom is supported by important classes of APIs including GUI, web browser, and OS APIs. Programs that use these APIs are prone to interference between a handler that is spinning an event loop and another handler that runs inside the loop. We present the first happens-before based race detection technique for such programs. Next, we consider the asynchronous programming model of modern languages like C]. In spite of providing primitives for the disciplined use of asynchrony, C] programs can deadlock because of incorrect use of blocking APIs along with non-blocking (asynchronous) APIs. We present the rst deadlock detection technique for asynchronous C] programs. We formulate necessary conditions for deadlock using a novel program representation that represents procedures and continuations, control ow between them and the threads on which they may be scheduled. We design a static analysis to construct the pro-gram representation and use it to identify deadlocks. Our ideas have resulted in research tools with practical impact. Sparse Racer, our tool to detect races, found 13 previously unknown use-after-free bugs in KDE Linux applications. Dead Wait, our deadlock detector, found 43 previously unknown deadlocks in asynchronous C] libraries. Developers have fixed 43 of these races and deadlocks, indicating that our techniques are useful in practice to detect bugs that developers consider worth fixing. Using large APIs effectively entails finding the right functionality and calling the methods that implement it correctly, possibly composing many API elements. Automatically infer-ring the information required to do this is a challenge that has attracted the attention of the research community. In response, the community has introduced many techniques to mine APIs and produce information ranging from usage examples and patterns, to protocols governing the API method calling sequences. We show how to mine unit tests to match API methods to their functional behaviour, for the specific but important class of math APIs. Math APIs are at the heart of many application domains ranging from machine learning to scientific computations, and are supplied by many competing libraries. In contrast to obtaining usage examples or identifying correct call sequences, the challenge in this domain is to infer API methods required to perform a particular mathematical computation, and to compose them correctly. We let developers specify mathematical computations naturally, as a math expression in the notation of interpreted languages (such as Matlab). Our unit test mining technique maps subexpressions to math API methods such that the method's functional behaviour matches the subexpression's executable semantics, as defined by the interpreter. We apply our technique, called MathFinder, to math API discovery and migration, and validate it in a user study. Developers who used MathFinder nished their programming tasks twice as fast as their counterparts who used the usual techniques like web and code search, and IDE code completion. We also demonstrate the use of MathFinder to assist in the migration of Weka, a popular machine learning library, to a different linear algebra library.

Os circuitos digitais cada vez mais são exigidos quanto ao desempenho e modularidade nos processos dos dias atuais. Para resolver estes processos, o comércio utiliza largamente circuitos digitais síncronos, que se baseiam no controle do sincronismo através de um relógio central. Esses circuitos, apesar de serem de fácil implementação e terem uma metodologia já conhecida, apresentam limitações quando se considera a distribuição dos sinais de sincronismo, a interferência do meio e os possíveis atrasos. Os circuitos assíncronos apresentam uma solução natural a essas exigências, uma vez que, possuem independência do sinal do relógio e toda sua construção é modular. Este trabalho apresenta um estudo comparativo de alguns estilos de projetos para construção de circuitos assíncronos utilizando dispositivos programados por lógica, PLDs, utilizando ferramentas de síntese lógica comerciais para circuitos síncronos. Esses circuitos assíncronos são descritos em VHDL para as células Muller, elementos M de N, registrador assíncrono, somadores e circuitos mais complexos em anel assíncrono e implementados em CPLDs e FPGAs. Os circuitos mais complexos são construídos em quatro estilos de projeto para os circuitos dos somadores: Descrição comportamental com indicação forte do sinal, DIMS, NCL e derivação a partir de circuito combinacional síncrono. Através dessa avaliação foi possível verificar as tendências do custo de elementos de programação e atrasos para realização de cálculos, frente aos circuitos síncronos similares. / This work presents a study about the implementation of asynchronous circuits on programmable devices platform. It investigates four different ways of implementing asynchronous circuits, including implementation of several different circuits in platforms provided by three different manufacturers. The implemented asynchronous circuits have a very poor performance when compared to their synchronous counterpart. However, this was expected as the platforms used were developed to be used with synchronous designs. The contributions of this work are in the following areas. First, it was described in detail how to implement VHDL code for self-timed designs. Second, different design were implemented to test the VHDL descriptions in the chosen platforms. Third, by comparing four different asynchronous styles, it is possible to find a style that is the more adequate for use in current FPGAs. Fourth, by analyzing the results obtained, it was possible to derive some conclusions on why asynchronous designs are so costly for these platforms and derive some suggestions to be used in the implementation of asynchronous FPGAs.

Os circuitos digitais cada vez mais são exigidos quanto ao desempenho e modularidade nos processos dos dias atuais. Para resolver estes processos, o comércio utiliza largamente circuitos digitais síncronos, que se baseiam no controle do sincronismo através de um relógio central. Esses circuitos, apesar de serem de fácil implementação e terem uma metodologia já conhecida, apresentam limitações quando se considera a distribuição dos sinais de sincronismo, a interferência do meio e os possíveis atrasos. Os circuitos assíncronos apresentam uma solução natural a essas exigências, uma vez que, possuem independência do sinal do relógio e toda sua construção é modular. Este trabalho apresenta um estudo comparativo de alguns estilos de projetos para construção de circuitos assíncronos utilizando dispositivos programados por lógica, PLDs, utilizando ferramentas de síntese lógica comerciais para circuitos síncronos. Esses circuitos assíncronos são descritos em VHDL para as células Muller, elementos M de N, registrador assíncrono, somadores e circuitos mais complexos em anel assíncrono e implementados em CPLDs e FPGAs. Os circuitos mais complexos são construídos em quatro estilos de projeto para os circuitos dos somadores: Descrição comportamental com indicação forte do sinal, DIMS, NCL e derivação a partir de circuito combinacional síncrono. Através dessa avaliação foi possível verificar as tendências do custo de elementos de programação e atrasos para realização de cálculos, frente aos circuitos síncronos similares. / This work presents a study about the implementation of asynchronous circuits on programmable devices platform. It investigates four different ways of implementing asynchronous circuits, including implementation of several different circuits in platforms provided by three different manufacturers. The implemented asynchronous circuits have a very poor performance when compared to their synchronous counterpart. However, this was expected as the platforms used were developed to be used with synchronous designs. The contributions of this work are in the following areas. First, it was described in detail how to implement VHDL code for self-timed designs. Second, different design were implemented to test the VHDL descriptions in the chosen platforms. Third, by comparing four different asynchronous styles, it is possible to find a style that is the more adequate for use in current FPGAs. Fourth, by analyzing the results obtained, it was possible to derive some conclusions on why asynchronous designs are so costly for these platforms and derive some suggestions to be used in the implementation of asynchronous FPGAs.

Os circuitos digitais cada vez mais são exigidos quanto ao desempenho e modularidade nos processos dos dias atuais. Para resolver estes processos, o comércio utiliza largamente circuitos digitais síncronos, que se baseiam no controle do sincronismo através de um relógio central. Esses circuitos, apesar de serem de fácil implementação e terem uma metodologia já conhecida, apresentam limitações quando se considera a distribuição dos sinais de sincronismo, a interferência do meio e os possíveis atrasos. Os circuitos assíncronos apresentam uma solução natural a essas exigências, uma vez que, possuem independência do sinal do relógio e toda sua construção é modular. Este trabalho apresenta um estudo comparativo de alguns estilos de projetos para construção de circuitos assíncronos utilizando dispositivos programados por lógica, PLDs, utilizando ferramentas de síntese lógica comerciais para circuitos síncronos. Esses circuitos assíncronos são descritos em VHDL para as células Muller, elementos M de N, registrador assíncrono, somadores e circuitos mais complexos em anel assíncrono e implementados em CPLDs e FPGAs. Os circuitos mais complexos são construídos em quatro estilos de projeto para os circuitos dos somadores: Descrição comportamental com indicação forte do sinal, DIMS, NCL e derivação a partir de circuito combinacional síncrono. Através dessa avaliação foi possível verificar as tendências do custo de elementos de programação e atrasos para realização de cálculos, frente aos circuitos síncronos similares. / This work presents a study about the implementation of asynchronous circuits on programmable devices platform. It investigates four different ways of implementing asynchronous circuits, including implementation of several different circuits in platforms provided by three different manufacturers. The implemented asynchronous circuits have a very poor performance when compared to their synchronous counterpart. However, this was expected as the platforms used were developed to be used with synchronous designs. The contributions of this work are in the following areas. First, it was described in detail how to implement VHDL code for self-timed designs. Second, different design were implemented to test the VHDL descriptions in the chosen platforms. Third, by comparing four different asynchronous styles, it is possible to find a style that is the more adequate for use in current FPGAs. Fourth, by analyzing the results obtained, it was possible to derive some conclusions on why asynchronous designs are so costly for these platforms and derive some suggestions to be used in the implementation of asynchronous FPGAs.

In broadband multimedia satellite networks it is necessary to multiplex bursty streams of traffic with differing Quality of Service (QoS) requirements to maximise the utilisation of the satellite link bandwidth. Providing the desired QoS of each service, in a multi-service environment is a major challenge for satellite networks. Asynchronous Transfer Mode (ATM) which provides hard QoS guarantees is suitable for a multi-service satellite environment. ATM has been developed as a vehicle for multimedia communications and is widely regarded as one of the most important and fastest-growing communications technology of this decade. The design of suitable traffic and congestion control algorithms is one of the most important challenge for the success of an ATM-based satellite network. This thesis develops and optimises a traffic and congestion control mechanism which can provide users the required QoS for ATM over satellite networks. In order to provide QoS differentiation for end-to-end communication it is proposed to use both loss and delay priorities, which are determined form the required Cell Loss Rate (CLR) and Cell Transfer Delay (CTD) parameters, for each service class. A multiple shared buffer scheduling (MSBS) policy considering both delay and loss priorities, is proposed and evaluated for scheduling and discarding of ATM cells. It is shown that both the CTD and CLR requirements of ATM services can be met by the MSBS scheme. A combined preventive/reactive control scheme incorporating an adaptive Leaky Bucket (LB) is investigated for the satellite environment. It has been found that reactive control improves the cell loss due to congestion for time scales larger than the propagation delay. As the satellite air interface bandwidth is currently one of the most expensive commodities in the service provision, an adaptive MAC protocol that can support the ATM service classes whilst maximising the bandwidth utilisation, is proposed and evaluated. The mapping of ATM service classes to MAC classes and the use of a prioritised request queue provides the QoS differentiation required by ATM networks. It is shown that a pure reservation system performs poorly for very bursty user traffic. The user population which can be supported using Random Access (RA) for very bursty users with short burst duration is higher. The system throughput can be maximised, by making this protocol adaptive to changing traffic characteristics. It is shown that the utilisation of the frame capacity and the total number of users served can be improved by using this protocol.

Intervals between data items propagating in self-timed circuits are controlled by handshake signals rather than by a clock. In many self-timed designs, a trailing data item will catch up with a leading item or token, even when it trails by thousands of gate delays. This effect, called "drafting," can be seen in many of the self-timed designs, e.g., GasP, Mousetrap, Click, and Micropipeline. The purpose of this dissertation is to reveal the circuit mechanism of drafting in self-timed circuits typically used in FIFO stages. Drafting is usually considered to be incidental to the operation of self-timed circuits since interval timing information is irrelevant to preservation of the proper order of data. However, if new applications of self-timed designs require preservation of timing between data items, or if interval data carries information, then the drafting mechanism must be understood to control it. Since drafting is an analog function in a digital circuit the effect may be used as a source of randomness or uniqueness. The drafting effect changes with manufacturing variability and each unit may provide a source for a unique digital signature that can be used in security applications.

No description available.

No description available.