Toward Effective Scalar Hardware for Highly Vectorizable Applications

The performance of a program will ultimately be limited by its serial (scalar) portion, as pointed out by Amdahl′s Law. Reported studies thus far of instruction-level parallelism have mixed data-parallel program portions with scalar program portions, often leading to contradictory and controversial results. We report an instruction-level behavioral characterization of scalar code containing minimal data-parallelism, extracted from highly vectorized programs of the PERFECT benchmark suite running on a Cray Y-MP system. We classify scalar basic blocks according to their instruction mix, characterize the data dependencies seen in each class, and, as a first step, measure the maximum intrablock instruction-level parallelism available. We observe skewed rather than balanced instruction distributions in scalar code and in individual basic block classes of scalar code; nonuniform distribution of parallelism across instruction classes; and, as expected, limited available intrablock parallelism. We identify frequently occurring data-dependence patterns and discuss new instructions to reduce latency. Toward effective scalar hardware, we study latency-pipelining trade-offs and restricted multiple instruction issue mechanisms.

Dynamic scheduling in manufacturing systems using brownian approximations

Recently, Brownian networks have emerged as an effective stochastic model to approximate multiclass queueing networks with dynamic scheduling capability, under conditions of balanced heavy loading. This paper is a tutorial introduction to dynamic scheduling in manufacturing systems using Brownian networks. The article starts with motivational examples. It then provides a review of relevant weak convergence concepts, followed by a description of the limiting behaviour of queueing systems under heavy traffic. The Brownian approximation procedure is discussed in detail and generic case studies are provided to illustrate the procedure and demonstrate its effectiveness. This paper places emphasis only on the results and aspires to provide the reader with an up-to-date understanding of dynamic scheduling based on Brownian approximations.

CM defect and Hilbert functions of monomial curves

In this article we consider a semigroup ring R = KGamma] of a numerical semigroup Gamma and study the Cohen- Macaulayness of the associated graded ring G(Gamma) := gr(m), (R) := circle plus(n is an element of N) m(n)/m(n+1) and the behaviour of the Hilbert function H-R of R. We define a certain (finite) subset B(Gamma) subset of F and prove that G(Gamma) is Cohen-Macaulay if and only if B(Gamma) = empty set. Therefore the subset B(Gamma) is called the Cohen-Macaulay defect of G(Gamma). Further, we prove that if the degree sequence of elements of the standard basis of is non-decreasing, then B(F) = empty set and hence G(Gamma) is Cohen-Macaulay. We consider a class of numerical semigroups Gamma = Sigma(3)(i=0) Nm(i) generated by 4 elements m(0), m(1), m(2), m(3) such that m(1) + m(2) = mo m3-so called ``balanced semigroups''. We study the structure of the Cohen-Macaulay defect B(Gamma) of Gamma and particularly we give an estimate on the cardinality |B(Gamma, r)| for every r is an element of N. We use these estimates to prove that the Hilbert function of R is non-decreasing. Further, we prove that every balanced ``unitary'' semigroup Gamma is ``2-good'' and is not ``1-good'', in particular, in this case, c(r) is not Cohen-Macaulay. We consider a certain special subclass of balanced semigroups Gamma. For this subclass we try to determine the Cohen-Macaulay defect B(Gamma) using the explicit description of the standard basis of Gamma; in particular, we prove that these balanced semigroups are 2-good and determine when exactly G(Gamma) is Cohen-Macaulay. (C) 2011 Published by Elsevier B.V.

Genetic search: Analysis using fitness moments

Genetic Algorithms are efficient and robust search methods that are being employed in a plethora of applications with extremely large search spaces. The directed search mechanism employed in Genetic Algorithms performs a simultaneous and balanced, exploration of new regions in the search space and exploitation of already discovered regions.This paper introduces the notion of fitness moments for analyzing the working of Genetic Algorithms (GAs). We show that the fitness moments in any generation may be predicted from those of the initial population. Since a knowledge of the fitness moments allows us to estimate the fitness distribution of strings, this approach provides for a method of characterizing the dynamics of GAs. In particular the average fitness and fitness variance of the population in any generation may be predicted. We introduce the technique of fitness-based disruption of solutions for improving the performance of GAs. Using fitness moments, we demonstrate the advantages of using fitness-based disruption. We also present experimental results comparing the performance of a standard GA and GAs (CDGA and AGA) that incorporate the principle of fitness-based disruption. The experimental evidence clearly demonstrates the power of fitness based disruption.

S-nets: A Petri net based model for performance evaluation of real-time scheduling algorithms

A new class of nets, called S-nets, is introduced for the performance analysis of scheduling algorithms used in real-time systems Deterministic timed Petri nets do not adequately model the scheduling of resources encountered in real-time systems, and need to be augmented with resource places and signal places, and a scheduler block, to facilitate the modeling of scheduling algorithms. The tokens are colored, and the transition firing rules are suitably modified. Further, the concept of transition folding is used, to get intuitively simple models of multiframe real-time systems. Two generic performance measures, called �load index� and �balance index,� which characterize the resource utilization and the uniformity of workload distribution, respectively, are defined. The utility of S-nets for evaluating heuristic-based scheduling schemes is illustrated by considering three heuristics for real-time scheduling. S-nets are useful in tuning the hardware configuration and the underlying scheduling policy, so that the system utilization is maximized, and the workload distribution among the computing resources is balanced.

Relay Load Balancing in Queued Cooperative Wireless Networks with Rateless Codes

Relay selection combined with buffering of packets of relays can substantially increase the throughput of a cooperative network that uses rateless codes. However, buffering also increases the end-to-end delays due to the additional queuing delays at the relay nodes. In this paper we propose a novel method that exploits a unique property of rateless codes that enables a receiver to decode a packet from non-contiguous and unordered portions of the received signal. In it, each relay, depending on its queue length, ignores its received coded bits with a given probability. We show that this substantially reduces the end-to-end delays while retaining almost all of the throughput gain achieved by buffering. In effect, the method increases the odds that the packet is first decoded by a relay with a smaller queue. Thus, the queuing load is balanced across the relays and traded off with transmission times. We derive explicit necessary and sufficient conditions for the stability of this system when the various channels undergo fading. Despite encountering analytically intractable G/GI/1 queues in our system, we also gain insights about the method by analyzing a similar system with a simpler model for the relay-to-destination transmission times.

A new approach to the design of electronic exchanges

Electronic Exchanges are double-sided marketplaces that allows multiple buyers to trade with multiple sellers, with aggregation of demand and supply across the bids to maximize the revenue in the market. In this paper, we propose a new design approach for an one-shot exchange that collects bids from buyers and sellers and clears the market at the end of the bidding period. The main principle of the approach is to decouple the allocation from pricing. It is well known that it is impossible for an exchange with voluntary participation to be efficient and budget-balanced. Budget-balance is a mandatory requirement for an exchange to operate in profit. Our approach is to allocate the trade to maximize the reported values of the agents. The pricing is posed as payoff determination problem that distributes the total payoff fairly to all agents with budget-balance imposed as a constraint. We devise an arbitration scheme by axiomatic approach to solve the payoff determination problem using the added-value concept of game theory.

Static Balancing of Spring-loaded Planar Revolute-joint Linkages without Auxiliary Links

We present a method to statically balance a general treestructured,planar revolute-joint linkage loaded with linear springs or constant forces without using auxiliary links. The balancing methods currently documented in the literature use extra links; some do not apply when there are spring loads and some are restricted to only two-link serial chains. In our method, we suitably combine any non-zero-free-length load spring with another spring to result in an effective zero-free-length spring load. If a link has a single joint (with the parent link), we give a procedure to attach extra zero-free-length springs to it so that forces and moments are balanced for the link. Another consequence of this attachment is that the constraint force of the joint on the parent link becomes equivalent to a zero-free-length spring load. Hence, conceptually,for the parent link, the joint with its child is removed and replaced with the zero-free-length spring. This feature allows recursive application of this procedure from the end-branches of the tree down to the root, satisfying force and moment balance of all the links in the process. Furthermore, this method can easily be extended to the closed-loop revolute-joint linkages, which is also illustrated in the paper.

Micro stepping of Shape Memory Alloy based Poly Phase motor

In literature we find broadly two types of shape memory alloy based motors namely limited rotation motor and unlimited rotation motor. The unlimited rotation type SMA based motor reported in literature uses SMA springs for actuation. An attempt has been made in this paper to develop an unlimited rotation type balanced poly phase motor based on SMA wire in series with a spring in each phase. By isolating SMA actuation and spring action we are able achieve a constant force by the SMA wire through out its range of operation. The Poly phase motor can be used in stepping mode for generating incremental motion and servo mode for generating continuous motion. A method of achieving servo motion by micro stepping is presented. Micro stepping consists of controlling single-phase temperature with a position feedback. The motor has been modeled with a new approach to the SMA wire Hysterysis model. Motor is simulated for different responses and the results are compared with the experimental data.

Broadcast in Adhoc Wireless Networks with Selfish Nodes: A Bayesian Incentive Compatibility Approach

We consider the incentive compatible broadcast (ICB) problem in ad hoc wireless networks with selfish nodes. We design a Bayesian incentive compatible broadcast (BIC-B) protocol to address this problem. VCG mechanism based schemes have been popularly used in the literature to design dominant strategy incentive compatible (DSIC) protocols for ad hoc wireless networks. VCG based mechanisms have two critical limitations: (i) the network is required to be bi-connected, (ii) the resulting protocol is not budget balanced. Our proposed BIC-B protocol overcomes these difficulties. We also prove the optimality of the proposed scheme.

Sliding mode control-based algorithms for consensus in connected swarms

In this article, finite-time consensus algorithms for a swarm of self-propelling agents based on sliding mode control and graph algebraic theories are presented. Algorithms are developed for swarms that can be described by balanced graphs and that are comprised of agents with dynamics of the same order. Agents with first and higher order dynamics are considered. For consensus, the agents' inputs are chosen to enforce sliding mode on surfaces dependent on the graph Laplacian matrix. The algorithms allow for the tuning of the time taken by the swarm to reach a consensus as well as the consensus value. As an example, the case when a swarm of first-order agents is in cyclic pursuit is considered.

Exploiting Programmable Network Interfaces for Parallel Query Execution in Workstation Clusters

Workstation clusters equipped with high performance interconnect having programmable network processors facilitate interesting opportunities to enhance the performance of parallel application run on them. In this paper, we propose schemes where certain application level processing in parallel database query execution is performed on the network processor. We evaluate the performance of TPC-H queries executing on a high end cluster where all tuple processing is done on the host processor, using a timed Petri net model, and find that tuple processing costs on the host processor dominate the execution time. These results are validated using a small cluster. We therefore propose 4 schemes where certain tuple processing activity is offloaded to the network processor. The first 2 schemes offload the tuple splitting activity - computation to identify the node on which to process the tuples, resulting in an execution time speedup of 1.09 relative to the base scheme, but with I/O bus becoming the bottleneck resource. In the 3rd scheme in addition to offloading tuple processing activity, the disk and network interface are combined to avoid the I/O bus bottleneck, which results in speedups up to 1.16, but with high host processor utilization. Our 4th scheme where the network processor also performs apart of join operation along with the host processor, gives a speedup of 1.47 along with balanced system resource utilizations. Further we observe that the proposed schemes perform equally well even in a scaled architecture i.e., when the number of processors is increased from 2 to 64

A hybrid nine-level inverter for IM drive

This paper proposes a new hybrid nine-level inverter topology for IM drive. The nine-level structure is realized by using two three-phase two-level inverters fed by isolated DC voltage sources and six H-bridges fed by capacitors. The number of switches required in this topology is only 36 where as the conventional nine-level topologies require 48 switches. The voltages across the capacitors, feeding the H-bridges that operate at asymmetric voltages, are effectively balanced by making use of the switching state redundancies. In this topology, the requirement of DC link voltage is only half of the maximum magnitude of the voltage space vector. As the two-level inverters are powered by isolated voltage sources, the circulation of triplen harmonic current in the motor winding is prevented. The proposed drive system is capable of functioning in three-level mode in case of any switch failure in H-bridges. The performance of the proposed topology in the entire modulation range is verified by simulation study and experiment.

Static balancing of a four-bar linkage and its cognates

Motivated by the need to statically balance the inherent elastic forces in linkages, this paper presents three techniques to statically balance a four-bar linkage loaded by a zero-free-length spring attached between its coupler point and an anchor point on the ground. The number of auxiliary links and balancing springs required for the three techniques is less than or equal to that of the only technique currently in the literature. One of the three techniques does not require auxiliary links. In these techniques, the set of values for the spring constants and the ground-anchor point of the balancing springs can vary over a one-parameter family. Thrice as many balancing choices are available when the cognates are considered. The ensuing numerous options enable a user to choose the most practical solution. To facilitate the evaluation of the balancing choices for all the cognates, Roberts-Chebyshev cognate theorem is extended to statically balanced four-bar linkages. (C) 2011 Elsevier Ltd. All rights reserved.

Passive vibration isolation of reaction wheel disturbances using a low frequency flexible space platform

Reaction wheel assemblies (RWAs) are momentum exchange devices used in fine pointing control of spacecrafts. Even though the spinning rotor of the reaction wheel is precisely balanced to minimize emitted vibration due to static and dynamic imbalances, precision instrument payloads placed in the neighborhood can always be severely impacted by residual vibration forces emitted by reaction wheel assemblies. The reduction of the vibration level at sensitive payloads can be achieved by placing the RWA on appropriate mountings. A low frequency flexible space platform consisting of folded continuous beams has been designed to serve as a mount for isolating a disturbance source in precision payloads equipped spacecrafts. Analytical and experimental investigations have been carried out to test the usefulness of the low frequency flexible platform as a vibration isolator for RWAs. Measurements and tests have been conducted at varying wheel speeds, to quantify and characterize the amount of isolation obtained from the reaction wheel generated vibration. These tests are further extended to other variants of similar design in order to bring out the best isolation for given disturbance loads. Both time and frequency domain analysis of test data show that the flexible beam platform as a mount for reaction wheels is quite effective and can be used in spacecrafts for passive vibration control. (C) 2011 Elsevier Ltd. All rights reserved.