Packet Reordering in Network Processors

Network processors today consist of multiple parallel processors (micro engines) with support for multiple threads to exploit packet level parallelism inherent in network workloads. With such concurrency, packet ordering at the output of the network processor cannot be guaranteed. This paper studies the effect of concurrency in network processors on packet ordering. We use a validated Petri net model of a commercial network processor, Intel IXP 2400, to determine the extent of packet reordering for IPv4 forwarding application. Our study indicates that in addition to the parallel processing in the network processor, the allocation scheme for the transmit buffer also adversely impacts packet ordering. In particular, our results reveal that these packet reordering results in a packet retransmission rate of up to 61%. We explore different transmit buffer allocation schemes namely, contiguous, strided, local, and global which reduces the packet retransmission to 24%. We propose an alternative scheme, packet sort, which guarantees complete packet ordering while achieving a throughput of 2.5 Gbps. Further, packet sort outperforms the in-built packet ordering schemes in the IXP processor by up to 35%.

Variable Granularity Access Tracking Scheme for Improving the Performance of Software Transactional Memory

Software transactional memory (STM) has been proposed as a promising programming paradigm for shared memory multi-threaded programs as an alternative to conventional lock based synchronization primitives. Typical STM implementations employ a conflict detection scheme, which works with uniform access granularity, tracking shared data accesses either at word/cache line or at object level. It is well known that a single fixed access tracking granularity cannot meet the conflicting goals of reducing false conflicts without impacting concurrency adversely. A fine grained granularity while improving concurrency can have an adverse impact on performance due to lock aliasing, lock validation overheads, and additional cache pressure. On the other hand, a coarse grained granularity can impact performance due to reduced concurrency. Thus, in general, a fixed or uniform granularity access tracking (UGAT) scheme is application-unaware and rarely matches the access patterns of individual application or parts of an application, leading to sub-optimal performance for different parts of the application(s). In order to mitigate the disadvantages associated with UGAT scheme, we propose a Variable Granularity Access Tracking (VGAT) scheme in this paper. We propose a compiler based approach wherein the compiler uses inter-procedural whole program static analysis to select the access tracking granularity for different shared data structures of the application based on the application's data access pattern. We describe our prototype VGAT scheme, using TL2 as our STM implementation. Our experimental results reveal that VGAT-STM scheme can improve the application performance of STAMP benchmarks from 1.87% to up to 21.2%.

New Concepts for Three-Dimensional Shape Analysis

A new approach to machine representation and analysis of three-dimensional objects is presented. The representation, based on the notion of "skeleton" of an object leads to a scheme for comparing two given object views for shape relations. The objects are composed of long, thin, rectangular prisms joined at their ends. The input picture to the program is the digitized line drawing portraying the three-dimensional object. To compare two object views, two characteristic vertices called "cardinal point" and "end-cardinal point," occurring consistently at the bends and open ends of the object are detected. The skeletons are then obtained as a connected path passing through these points. The shape relationships between the objects are then obtained from the matching characteristics of their skeletons. The method explores the possibility of a more detailed and finer analysis leading to detection of features like symmetry, asymmetry and other shape properties of an object.

Composite instantaneous comparators basis for design and their transient performance

Principles of design of composite instantaneous comparators (a combination of amplitude- and phase- comparison techniques) are laid out to provide directional, directional-reactance, nonoffset-resistance and conductance characteristices. The respective signals provided by the voltage transformer and the current transformer are directly used as relaying signals without resorting to any form of mixing. Phase shifts required, are obtained by using magnetic ferrite cores in a novel manner. Sampling units employing a combination of ferrite cores and semiconductor devices provide highly reliable designs. Special attention is paid to the choice of relaying signals, to eliminate the need for any synchronisation or modification and to avoid `image¿ characteristics. These factors have resulted in a considerable simplification of the practical circuitry. A thyristor AND circuit is employed in dual comparator units to provide the final tripping, and leads to a circuit which is much less sensitive to extraneous signals than a single-thyristor unit.

Supercapacitor studies on globular polypyrrole microstructures developed by a facile electrochemical route

Micrometre-scale polypyrrole (PPy) structures are synthesised for electrochemical supercapacitor applications by a facile electrochemical route. Globular polypyrrole microstructures of size < 5 μm are grown on stainless steel (SS-304) substrate by electro-polymerisation of pyrrole on oxygen microbubble templates electrochemically generated and stabilised in the presence of surfactant/supporting electrolyte/ dopant b-naphthalene sulfonic acid (b-NSA). Microstructures obtained with scan range of 0??1.6 V (against Ag/AgCl) are uniformly distributed over the surface with high coverage density of 5 x 105 to 8 x 10 cm-2. Fourier transform infrared spectroscopy and X-ray photoelectron spectroscopy revealed that the formed microstructures are of Β-NSA doped PPy. Scanning electron microscopy showed the uniform spread and good coverage of microstructures over the substrate. Supercapacitor properties of PPy films are investigated by cyclic voltammetry, electrochemical impedance spectroscopy and galvanostatic charge/discharge methods with 1.0 M KCl as electrolyte in a three-electrode electrochemical cell. Specific capacitance of 583 Fg-1 is obtained, which is greater than the values (350-400 Fg-1 highest) usually reported for this material. Electrochemical impedance spectroscopy proves the superc

Microprocessor-Based Field-Oriented Control of A CSI-Fed Induction Motor Drive

This paper describes the method of field orientation of the stator current vector with respect to the stator, mutual, and rotor flux vectors, for the control of an induction motor fed from a current source inverter (CSI). A control scheme using this principle is described for orienting the stator current with respect to the rotor flux, as this gives natural decoupling between the current coordinates. A dedicated micro-computer system developed for implementing this scheme has been described. The experimental results are also presented.

Three-system and single-system static distance relays

Static distance relays employing semiconductor devices as their active elements offer many advantages over the conventional electromagnetic and rectifier relays. The paper describes single-system and three-system static distance relays, which depend for their operation on the instantaneous-comparison or `block-spike¿ scheme. Design principles and typical discriminating and logic circuits are described for the new relaying equipment. The relaying circuitry has been devised for obtaining uniform performance on all kinds of faults, by the use of two phase detectors¿one for multiphase faults and one for earth faults. The phase detector for multiphase faults provides an improved polar characteristic in the complex-impedance plane, which fits only around the fault area of a transmission line. The other features of the relay are: reliable pickup for close-in faults, least susceptibility to maloperation under power-swing conditions, and reduction in cost and panel space required. The operating characteristics of the relays, as expressed by accuracy/range charts, are also presented.

Bypass operation in bridge convertors for high-voltage d.c. transmission

Bypass operation with the aid of a special bypass valve is an important part of present-day schemes of protection for h.v. d.c. transmission systems. In this paper, the possibility of using two valves connected to any phase in the bridge convertor for the purpose of bypass operation is studied. The scheme is based on the use of logic circuits in conjunction with modified methods of fault detection. Analysis of the faults in a d.c. transmission system is carried out with the object of determining the requirements of such a logic-circuit control system. An outline of the scheme for the logic-circuit control of the bypass operation for both rectifier and invertor bridges is then given. Finally, conclusions are drawn regarding the advantages of such a system, which include reduction in the number of valves, prevention of severe faults and fast clearance of faults, in addition to the immediate location of the fault and its nature.

Performance evaluation of neural network algorithms for multisensor data fusion in an airborne track while scan radar

This paper deals with the solution to the problem of multisensor data fusion for a single target scenario as detected by an airborne track-while-scan radar. The details of a neural network implementation, various training algorithms based on standard backpropagation, and the results of training and testing the neural network are presented. The promising capabilities of RPROP algorithm for multisensor data fusion for various parameters are shown in comparison to other adaptive techniques

Large improvements in application throughput of long-running multi-component applications using batch grids

Computational grids with multiple batch systems (batch grids) can be powerful infrastructures for executing long-running multi-component parallel applications. In this paper, we evaluate the potential improvements in throughput of long-running multi-component applications when the different components of the applications are executed on multiple batch systems of batch grids. We compare the multiple batch executions with executions of the components on a single batch system without increasing the number of processors used for executions. We perform our analysis with a foremost long-running multi-component application for climate modeling, the Community Climate System Model (CCSM). We have built a robust simulator that models the characteristics of both the multi-component application and the batch systems. By conducting large number of simulations with different workload characteristics and queuing policies of the systems, processor allocations to components of the application, distributions of the components to the batch systems and inter-cluster bandwidths, we show that multiple batch executions lead to 55% average increase in throughput over single batch executions for long-running CCSM. We also conducted real experiments with a practical middleware infrastructure and showed that multi-site executions lead to effective utilization of batch systems for executions of CCSM and give higher simulation throughput than single-site executions. Copyright (c) 2011 John Wiley & Sons, Ltd.

Race Detection for Android Applications

Programming environments for smartphones expose a concurrency model that combines multi-threading and asynchronous event-based dispatch. While this enables the development of efficient and feature-rich applications, unforeseen thread interleavings coupled with non-deterministic reorderings of asynchronous tasks can lead to subtle concurrency errors in the applications. In this paper, we formalize the concurrency semantics of the Android programming model. We further define the happens-before relation for Android applications, and develop a dynamic race detection technique based on this relation. Our relation generalizes the so far independently studied happens-before relations for multi-threaded programs and single-threaded event-driven programs. Additionally, our race detection technique uses a model of the Android runtime environment to reduce false positives. We have implemented a tool called DROIDRACER. It generates execution traces by systematically testing Android applications and detects data races by computing the happens-before relation on the traces. We analyzed 1 5 Android applications including popular applications such as Facebook, Twitter and K-9 Mail. Our results indicate that data races are prevalent in Android applications, and that DROIDRACER is an effective tool to identify data races.

Compiler/Runtime Framework for Dynamic Dataflow Parallelization of Tiled Programs

Task-parallel languages are increasingly popular. Many of them provide expressive mechanisms for intertask synchronization. For example, OpenMP 4.0 will integrate data-driven execution semantics derived from the StarSs research language. Compared to the more restrictive data-parallel and fork-join concurrency models, the advanced features being introduced into task-parallelmodels in turn enable improved scalability through load balancing, memory latency hiding, mitigation of the pressure on memory bandwidth, and, as a side effect, reduced power consumption. In this article, we develop a systematic approach to compile loop nests into concurrent, dynamically constructed graphs of dependent tasks. We propose a simple and effective heuristic that selects the most profitable parallelization idiom for every dependence type and communication pattern. This heuristic enables the extraction of interband parallelism (cross-barrier parallelism) in a number of numerical computations that range from linear algebra to structured grids and image processing. The proposed static analysis and code generation alleviates the burden of a full-blown dependence resolver to track the readiness of tasks at runtime. We evaluate our approach and algorithms in the PPCG compiler, targeting OpenStream, a representative dataflow task-parallel language with explicit intertask dependences and a lightweight runtime. Experimental results demonstrate the effectiveness of the approach.

Multithreaded Test Synthesis for Deadlock Detection

Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing software testing and/or dynamic analysis to detect. deadlocks. Their effectiveness is dependent on well-designed multithreaded test cases. Unsurprisingly, developing multithreaded tests is significantly harder than developing sequential tests for obvious reasons. In this paper, we address the problem of automatically synthesizing multithreaded tests that can induce deadlocks. The key insight to our approach is that a subset of the properties observed when a deadlock manifests in a concurrent execution can also be observed in a single threaded execution. We design a novel, automatic, scalable and directed approach that identifies these properties and synthesizes a deadlock revealing multithreaded test. The input to our approach is the library implementation under consideration and the output is a set of deadlock revealing multithreaded tests. We have implemented our approach as part of a tool, named OMEN1. OMEN is able to synthesize multithreaded tests on many multithreaded Java libraries. Applying a dynamic deadlock detector on the execution of the synthesized tests results in the detection of a number of deadlocks, including 35 real deadlocks in classes documented as thread-safe. Moreover, our experimental results show that dynamic analysis on multithreaded tests that are either synthesized randomly or developed by third-party programmers are ineffective in detecting the deadlocks.

Synthesizing Racy Tests

Subtle concurrency errors in multithreaded libraries that arise because of incorrect or inadequate synchronization are often difficult to pinpoint precisely using only static techniques. On the other hand, the effectiveness of dynamic race detectors is critically dependent on multithreaded test suites whose execution can be used to identify and trigger races. Usually, such multithreaded tests need to invoke a specific combination of methods with objects involved in the invocations being shared appropriately to expose a race. Without a priori knowledge of the race, construction of such tests can be challenging. In this paper, we present a lightweight and scalable technique for synthesizing precisely these kinds of tests. Given a multithreaded library and a sequential test suite, we describe a fully automated analysis that examines sequential execution traces, and produces as its output a concurrent client program that drives shared objects via library method calls to states conducive for triggering a race. Experimental results on a variety of well-tested Java libraries yield 101 synthesized multithreaded tests in less than four minutes. Analyzing the execution of these tests using an off-the-shelf race detector reveals 187 harmful races, including several previously unreported ones.