Improved preprocessing methods for modulo scheduling algorithms

Instruction scheduling with an automaton-based resource conflict model is well-established for normal scheduling. Such models have been generalized to software pipelining in the modulo-scheduling framework. One weakness with existing methods is that a distinct automaton must be constructed for each combination of a reservation table and initiation interval. In this work, we present a different approach to model conflicts. We construct one automaton for each reservation table which acts as a compact encoding of all the conflict automata for this table, which can be recovered for use in modulo-scheduling. The basic premise of the construction is to move away from the Proebsting-Fraser model of conflict automaton to the Muller model of automaton modelling issue sequences. The latter turns out to be useful and efficient in this situation. Having constructed this automaton, we show how to improve the estimate of resource constrained initiation interval. Such a bound is always better than the average-use estimate. We show that our bound is safe: it is always lower than the true initiation interval. This use of the automaton is orthogonal to its use in modulo-scheduling. Once we generate the required information during pre-processing, we can compute the lower bound for a program without any further reference to the automaton.

I*(P-2(1/2)) production from CH3I photodissociation at 236 nm

The quantum yield of I*((2)p(1/2)) production from CH3I photolysis at 236 nm in the gas phase has been measured as 0.69 +/- 0.03. The implication is that direct excitation to the (1)Q(1) excited state is significant at this wavelength. The dynamics of I* formation at other excitation energies covering the entire A-band of absorption of CH3I has been discussed in the light of this measurement.

Scheduling expression trees for delayed-load architectures

In this paper we consider the problem of scheduling expression trees on delayed-load architectures. The problem tackled here takes root from the one considered in [Proceedings of the ACM SIGPLAN '91 Conf. on Programming Language Design and Implementation, 1991. p. 256] in which the leaves of the expression trees all refer to memory locations. A generalization of this involves the situation in which the trees may contain register variables, with the registers being used only at the leaves. Solutions to this generalization are given in [ACM Trans. Prog. Lang. Syst. 17 (1995) 740, Microproc. Microprog. 40 (1994) 577]. This paper considers the most general case in which the registers are reusable. This problem is tackled in [Comput. Lang, 21 (1995) 49] which gives an approximate solution to the problem under certain assumptions about the contiguity of the evaluation order: Here we propose an optimal solution (which may involve even a non-contiguous evaluation of the tree). The schedule generated by the algorithm given in this paper is optimal in the sense that it is an interlock-free schedule which uses the minimum number of registers required. An extension to the algorithm incorporates spilling. The problem as stated in this paper is an instruction scheduling problem. However, the problem could also be rephrased as an operations research problem with a difference in terminology. (C) 2002 Elsevier Science B.V. All rights reserved.

The production of AlN-rich matrix composites by the reactive infiltration of Al alloys in nitrogen

Aluminium nitride (AlN)-Al matrices reinforced with Al2O3 particulate have been fabricated by reactive infiltration of Al-2% Mg alloy into Al2O3 preforms in N-2 in the temperature range of 900-1075 degreesC. The growth of composites of useful thickness was facilitated by the presence of a Mg-rich external getter, in the absence of which composite growth is self-limiting and terminates prematurely. Successful growth of composites has been attributed to the reduction in residual oxygen partial pressure brought about by the reaction with oxygen of highly volatile Mg in the getter alloy. The microstructure of the matrix consists of AlN-rich regions contiguous with the particulate with metal-rich channels in-between, thereby suggesting that nitridation initiates by preferential wicking of alloy along the particle surfaces. The increase in nitride content of the matrix with temperature is consistent with hardness values that vary between similar to3 and 10 GPa. (C) 2002 Acta Materialia Inc. Published by Elsevier Science Ltd. All rights reserved.

Optimal scheduling of multiple chlorine sources in water distribution systems

The specified range of free chlorine residual (between minimum and maximum) in water distribution systems needs to be maintained to avoid deterioration of the microbial quality of water, control taste and/or odor problems, and hinder formation of carcino-genic disinfection by-products. Multiple water quality sources for providing chlorine input are needed to maintain the chlorine residuals within a specified range throughout the distribution system. The determination of source dosage (i.e., chlorine concentrations/chlorine mass rates) at water quality sources to satisfy the above objective under dynamic conditions is a complex process. A nonlinear optimization problem is formulated to determine the chlorine dosage at the water quality sources subjected to minimum and maximum constraints on chlorine concentrations at all monitoring nodes. A genetic algorithm (GA) approach in which decision variables (chlorine dosage) are coded as binary strings is used to solve this highly nonlinear optimization problem, with nonlinearities arising due to set-point sources and non-first-order reactions. Application of the model is illustrated using three sample water distribution systems, and it indicates that the GA,is a useful tool for evaluating optimal water quality source chlorine schedules.

Sustainable biomass production for energy in selected Asian countries

This paper presents a synthesis of assessment of sustainable biomass production potential in six Asian countries-China, India, Malaysia, Philippines, Sri Lanka and Thailand, and is based on the detailed studies carried out in these countries under the Asian Regional Research Programme in Energy, Environment and Climate (ARRPEEC). National level studies were undertaken to estimate land availability for biomass production, identify and evaluate the biomass production options in terms of yield per hectare and financial viability, estimate sustainable biomass production for energy, and estimate the energy potential of biomass production in the six Asian countries. Sustainable biomass production from plantation is estimated to be in the range of 182.5-210.5, 62-310, 0.4-1.7, 3.7-20.4, 2.0-9.9 and 11.6-106.6 Mt yr(-1) for China, India, Malaysia, Philippines, Sri Lanka and Thailand, respectively. The maximum annual electricity generation potential, using advanced technologies, from the sustainable biomass production is estimated to be about 27, 114, 4.5, 79, 254 and 195 percentage of the total electricity generation in year 2000 in China, India, Malaysia, Philippines, Sri Lanka and Thailand, respectively. Investment cost for bioenergy production varies from US$381 to 1842 ha(-1) in the countries considered in this study; investment cost for production of biomass varies from US$5.1 to 23 t(-1). (C) 2003 Elsevier Ltd. All rights reserved.

Optimal Sleep-Wake Scheduling for Quickest Intrusion Detection using wireless sensor Networks

We consider the problem of quickest detection of an intrusion using a sensor network, keeping only a minimal number of sensors active. By using a minimal number of sensor devices,we ensure that the energy expenditure for sensing, computation and communication is minimized (and the lifetime of the network is maximized). We model the intrusion detection (or change detection) problem as a Markov decision process (MDP). Based on the theory of MDP, we develop the following closed loop sleep/wake scheduling algorithms: 1) optimal control of Mk+1, the number of sensors in the wake state in time slot k + 1, 2) optimal control of qk+1, the probability of a sensor in the wake state in time slot k + 1, and an open loop sleep/wake scheduling algorithm which 3) computes q, the optimal probability of a sensor in the wake state (which does not vary with time),based on the sensor observations obtained until time slot k.Our results show that an optimum closed loop control onMk+1 significantly decreases the cost compared to keeping any number of sensors active all the time. Also, among the three algorithms described, we observe that the total cost is minimum for the optimum control on Mk+1 and is maximum for the optimum open loop control on q.

An Efficient and Optimized Bluetooth Scheduling Algorithm for Scatternets

Bluetooth is a short-range radio technology operating in the unlicensed industrial-scientific-medical (ISM) band at 2.45 GHz. A scatternet is established by linking several piconets together in ad hoc fashion to yield a global wireless ad hoc network. This paper proposes a polling policy that aims to achieve increased system throughput and reduced packet delays while providing reasonably good fairness among all traffic flows in a Bluetooth Scatternet. Experimental results from our proposed algorithm show performance improvements over a well known existing algorithm.

Automatic Compilation of MATLAB Programs for Synergistic Execution on Heterogeneous Processors

MATLAB is an array language, initially popular for rapid prototyping, but is now being increasingly used to develop production code for numerical and scientific applications. Typical MATLAB programs have abundant data parallelism. These programs also have control flow dominated scalar regions that have an impact on the program's execution time. Today's computer systems have tremendous computing power in the form of traditional CPU cores and throughput oriented accelerators such as graphics processing units(GPUs). Thus, an approach that maps the control flow dominated regions to the CPU and the data parallel regions to the GPU can significantly improve program performance. In this paper, we present the design and implementation of MEGHA, a compiler that automatically compiles MATLAB programs to enable synergistic execution on heterogeneous processors. Our solution is fully automated and does not require programmer input for identifying data parallel regions. We propose a set of compiler optimizations tailored for MATLAB. Our compiler identifies data parallel regions of the program and composes them into kernels. The problem of combining statements into kernels is formulated as a constrained graph clustering problem. Heuristics are presented to map identified kernels to either the CPU or GPU so that kernel execution on the CPU and the GPU happens synergistically and the amount of data transfer needed is minimized. In order to ensure required data movement for dependencies across basic blocks, we propose a data flow analysis and edge splitting strategy. Thus our compiler automatically handles composition of kernels, mapping of kernels to CPU and GPU, scheduling and insertion of required data transfer. The proposed compiler was implemented and experimental evaluation using a set of MATLAB benchmarks shows that our approach achieves a geometric mean speedup of 19.8X for data parallel benchmarks over native execution of MATLAB.

New Ventures’ influence on the Growth of SME Employment, Production and Exports in India: Does Institutional Credit matter?

New ventures are considered to be a major source of small firm growth. In Indian context the contribution of new ventures in terms of new employment, production and exports has largely remained unexplored. It is equally important and unexplored, the significance of the contribution of bank credit to the growth of new ventures in India. This paper is an attempt to throw light on these two aspects. The research is based on secondary data of the liberalized period provided by Ministry of Micro, Small and Medium Enterprises, Government of India and Reserve Bank of India. To analyze the influence of bank credit growth on new ventures and the influence of new ventures on growth of additional employment, additional production and additional exports, we used a Bi-Variate Vector Auto Regression. Based on the model generated, Granger causality tests are conducted to obtain the results. The study found that rate of growth of bank credit causes the number of new ventures, implying any increase in the rate of growth of bank credit will be beneficial to the growth of new ventures. The study also concluded that new ventures are not causing the growth of additional employment or additional production. However new ventures cause the growth of additional exports. This is reasonable as entrepreneurs start their new ventures with minimum possible employment and relatively low rate of capacity utilization and they come up to take advantage of the process of globalization by catering to the international market.

STEM+: A Fair and Efficient Algorithm for Scheduling on the DSCH in UMTS Networks

In Universal Mobile Telecommunication Systems (UMTS), the Downlink Shared Channel (DSCH) can be used for providing streaming services. The traffic model for streaming services is different from the commonly used continuously- backlogged model. Each connection specifies a required service rate over an interval of time, k, called the "control horizon". In this paper, our objective is to determine how k DSCH frames should be shared among a set of I connections. We need a scheduler that is efficient and fair and introduce the notion of discrepancy to balance the conflicting requirements of aggregate throughput and fairness. Our motive is to schedule the mobiles in such a way that the schedule minimizes the discrepancy over the k frames. We propose an optimal and computationally efficient algorithm, called STEM+. The proof of the optimality of STEM+, when applied to the UMTS rate sets is the major contribution of this paper. We also show that STEM+ performs better in terms of both fairness and aggregate throughput compared to other scheduling algorithms. Thus, STEM+ achieves both fairness and efficiency and is therefore an appealing algorithm for scheduling streaming connections.

Power control and transmission scheduling for network utility maximization in wireless networks

We consider a joint power control and transmission scheduling problem in wireless networks with average power constraints. While the capacity region of a wireless network is convex, a characterization of this region is a hard problem. We formulate a network utility optimization problem involving time-sharing across different "transmission modes," where each mode corresponds to the set of power levels used in the network. The structure of the optimal solution is a time-sharing across a small set of such modes. We use this structure to develop an efficient heuristic approach to finding a suboptimal solution through column generation iterations. This heuristic approach converges quite fast in simulations, and provides a tool for wireless network planning.

Opportunistic scheduling of wireless links

We consider the problem of scheduling of a wireless channel (server) to several queues. Each queue has its own link (transmission) rate. The link rate of a queue can vary randomly from slot to slot. The queue lengths and channel states of all users are known at the beginning of each slot. We show the existence of an optimal policy that minimizes the long term (discounted) average sum of queue lengths. The optimal policy, in general needs to be computed numerically. Then we identify a greedy (one step optimal) policy, MAX-TRANS which is easy to implement and does not require the channel and traffic statistics. The cost of this policy is close to optimal and better than other well-known policies (when stable) although it is not throughput optimal for asymmetric systems. We (approximately) identify its stability region and obtain approximations for its mean queue lengths and mean delays. We also modify this policy to make it throughput optimal while retaining good performance.