Register Allocation and Optimal Spill code Scheduling in Software Pipelined Loops using 0-1 Integer Linear Programming Formulation

In achieving higher instruction level parallelism, software pipelining increases the register pressure in the loop. The usefulness of the generated schedule may be restricted to cases where the register pressure is less than the available number of registers. Spill instructions need to be introduced otherwise. But scheduling these spill instructions in the compact schedule is a difficult task. Several heuristics have been proposed to schedule spill code. These heuristics may generate more spill code than necessary, and scheduling them may necessitate increasing the initiation interval. We model the problem of register allocation with spill code generation and scheduling in software pipelined loops as a 0-1 integer linear program. The formulation minimizes the increase in initiation interval (II) by optimally placing spill code and simultaneously minimizes the amount of spill code produced. To the best of our knowledge, this is the first integrated formulation for register allocation, optimal spill code generation and scheduling for software pipelined loops. The proposed formulation performs better than the existing heuristics by preventing an increase in II in 11.11% of the loops and generating 18.48% less spill code on average among the loops extracted from Perfect Club and SPEC benchmarks with a moderate increase in compilation time.

An optimal weighted-average congestion based pricing scheme for enhanced QoS, , LNCS 4882, 2007

Pricing is an effective tool to control congestion and achieve quality of service (QoS) provisioning for multiple differentiated levels of service. In this paper, we consider the problem of pricing for congestion control in the case of a network of nodes under a single service class and multiple queues, and present a multi-layered pricing scheme. We propose an algorithm for finding the optimal state dependent price levels for individual queues, at each node. The pricing policy used depends on a weighted average queue length at each node. This helps in reducing frequent price variations and is in the spirit of the random early detection (RED) mechanism used in TCP/IP networks. We observe in our numerical results a considerable improvement in performance using our scheme over that of a recently proposed related scheme in terms of both throughput and delay performance. In particular, our approach exhibits a throughput improvement in the range of 34 to 69 percent in all cases studied (over all routes) over the above scheme.

Compiler-Directed Dynamic Voltage Scaling using Program Phases

Energy consumption has become a major constraint in providing increased functionality for devices with small form factors. Dynamic voltage and frequency scaling has been identified as an effective approach for reducing the energy consumption of embedded systems. Earlier works on dynamic voltage scaling focused mainly on performing voltage scaling when the CPU is waiting for memory subsystem or concentrated chiefly on loop nests and/or subroutine calls having sufficient number of dynamic instructions. This paper concentrates on coarser program regions and for the first time uses program phase behavior for performing dynamic voltage scaling. Program phases are annotated at compile time with mode switch instructions. Further, we relate the Dynamic Voltage Scaling Problem to the Multiple Choice Knapsack Problem, and use well known heuristics to solve it efficiently. Also, we develop a simple integer linear program formulation for this problem. Experimental evaluation on a set of media applications reveal that our heuristic method obtains a 38% reduction in energy consumption on an average, with a performance degradation of 1% and upto 45% reduction in energy with a performance degradation of 5%. Further, the energy consumed by the heuristic solution is within 1% of the optimal solution obtained from the ILP approach.

The Future of Product Development in India

A product is reflects the constraints, beliefs and aspirations of a society. Product development both influences and is influenced by the growth of a society and its economy. India is a fast growing economy. We use a brief historical, socioeconomic account of India as a backdrop to detect the drivers and roadblocks to its economic and social growth. In this context, current and future trends of PD practice, education and research are sketched. Products are taken as artefacts of the act of designing, without limiting to only those created by industry in a market-economic context.

An Efficient Distributed Scheme for Source Routing Protocol in Communication Networks

In this paper, we propose an efficient source routing algorithm for unicast flows, which addresses the scalability problem associated with the basic source routing technique. Simulation results indicate that the proposed algorithm indeed helps in reducing the message overhead considerably, and at the same time it gives comparable performance in terms of resource utilization across a wide range of workloads.

Influence of ethanol/water mixture on the undrained shear strength of pure clays

The mechanical properties of clays are highly dependent not only on the stress/strain ratio to which the material is subjected but also on the chemistry of the pore fluids which in turn affects the intergranular or the effective stresses. Atterberg limits and vane shear tests were performed with different pore fluids in order to observe how the fine-grained material mechanically responded. The diffuse double layer theory has been used to interpret the data of vane shear tests in order to explain the variation of geotechnical responses with the different clays. Van der Waals forces and double layer forces were obtained and capillary forces calculated. The results show that while for kaolinite and illite the chemistry of the pore fluids has no influence on the water content and hence on the mechanical behaviour of the material, Na-smectite shows a strong correlation between the dielectric constant of the pore fluids and an increase in undrained shear strength. The data obtained extends an understanding of the influence of the dielectric constant (epsilon) of the pore fluids on the geotechnical properties of fine-grained materials.

Sensitive Liquid Chromatography-Tandem Mass Spectrometry Method for the Determination of Olanzapine in Human Urine

A sensitive and selective liquid chromatographic-tandem mass spectrometric (LC-MS-MS) method was developed to determine olanzapine (OLZ) in human urine. After solid-phase extraction with SPE cartridge, the urine sample was analysed on a C-18 column (Symmetry 3.5 mu m, 50 x 4.6 mm i.d) interfaced with a triple quadrupole tandem mass spectrometer. Positive electrospray ionization was employed as the ionization source. The mobile phase consisted of ammonium acetate (pH 7.8)-acetonitrile (10:90, v/v). The method was linear over a concentration range of 1-100 ngml(-1). The lower limit of quantitation was 1 ngml(-1). The intra-day and inter-day relative standard deviation across three validation runs over the entire concentration range was < 11.5 %. The accuracy determined at three concentrations (8.0, 50.0 and 85.0 ngml(-1) OLZ) was within +/- 1.21 % in terms of relative errors.

Photocatalytic degradation of gaseous toluene by using immobilized titania/silica on aluminum sheets

The aim of this study was to prepare a highly active immobilized titania/silica photocatalyst and to test its performance in situ toward degradation of toluene as one of the major toxic indoor contaminants. In this work, two different titania layers immobilized on Al sheets were synthesized via low temperature sol-gel method employing presynthesized highly active titania powders (Degussa P25 and Millennium PC500, mass ratio 1:1): (a) with a silica/titania binder and a protective layer and (b) without the binder. The photocatalysts were characterized by X-ray diffraction, nitrogen sorption measurements, scanning electron microscopy (SEM), infrared spectroscopy, and UV-vis diffuse reflectance spectroscopy (DRS). The in situ photocatalytic degradation of gaseous toluene was selected as a probe reaction to test photocatalytic activity and to verify the potential application of these materials for air remediation. Results show that nontransparent highly photocatalytically active coatings based on the silica/titania binder and homogeneously dispersed TiO2 powders were obtained on the Al sheets. The crystalline structure of titania was not altered upon addition of the binder, which also prevented inhomogeneous agglomeration of particles on the photocatalyst surface. The photoactivity results indicate that the adsorption properties and photocatalytic activity of immobilized photocatalysts with the silica/titania binder and an underlying protective layer were very effective and additionally, they exhibited considerably improved adhesion and uniformity. We present a new highly photocatalytically active immobilized catalyst on a convenient metallic support, which has a potential application in an air cleaning device.

Effect of high gold salt concentrations on the size and polydispersity of gold nanoparticles prepared by an extended Turkevich-Frens method

The Turkevich-Frens synthesis starting conditions are expanded, ranging the gold salt concentrations up to 2 mM and citrate/gold(III) molar ratios up to 18:1. For each concentration of the initial gold salt solution, the citrate/gold(III) molar ratios are systematically varied from 2:1 to 18:1 and both the size and size distribution of the resulting gold nanoparticles are compared. This study reveals a different nanoparticle size evolution for gold salt solutions ranging below 0.8 mM compared to the case of gold salt solutions above 0.8 mM. In the case of Au3+]<0.8 mM, both the size and size distribution vary substantially with the citrate/gold(III) ratio, both displaying plateaux that evolve inversely to Au3+] at larger ratios. Conversely, for Au3+]>= 0.8 mM, the size and size distribution of the synthesized gold nanoparticles continuously rise as the citrate/gold(III) ratio is increased. A starting gold salt concentration of 0.6 mM leads to the formation of the most monodisperse gold nanoparticles (polydispersity index<0.1) for a wide range of citrate/gold(III) molar ratios (from 4:1 to 18:1). Via a model for the formation of gold nanoparticles by the citrate method, the experimental trends in size could be qualitatively predicted:the simulations showed that the destabilizing effect of increased electrolyte concentration at high initial Au3+] is compensated by a slight increase in zeta potential of gold nanoparticles to produce concentrated dispersion of gold nanoparticles of small sizes.

PEO|Sncl(2)|PANI composites: as an electrolyte in solid-state battery

Solid-state polymer electrolytes possess high conductivity and have advantages compared with their liquid counterparts. The polyethylene oxide (PEO)-based polymer is a good candidate for this purpose. The PEO/SnCl2/polyaniline composite (PSP composites) at different weight percentages were prepared in anhydrous acetonitrile media. Structural studies were carried out of the prepared composites by X-ray diffraction, Fourier transmission infrared spectroscopy, and surface morphology by scanning electron microscopy. The sigma (dc) was carried out by a two-probe method, and it is found that the conductivity increases with an increase in temperature. The temperature-dependent conductivity of the composites exhibits a typical semi-conducting behavior and hence can be explained by the 1D variable range hopping model proposed by Mott. The electrochemical cell parameters for battery applications at room temperature have also been determined. The samples are fabricated for battery application in the configuration of Na: (PSP): (I-2 + C + sample), and their experimental data are measured using Wagner's polarization technique. The cell parameters result in an open-circuit voltage of 0.83 V and a short-circuit current of 912 mu A for PSP (70:30:10) composite. Hence, these composites can be used in polymer electrolyte studies.

Electrical transport characteristics of ZnO-Bi2O3-B2O3 glasses

Optically clear glasses in the ZnO-Bi2O3-B2O3 (ZBBO) system were fabricated via the conventional melt-quenching technique. Dielectric constant and loss measurements carried out on ZBBO glasses unraveled nearly frequency (1 kHz-10 MHz)-independent dielectric characteristics associated with significantly low loss (D = 0.004). However, weak temperature response was found with temperature coefficient of dielectric constant 18 +/- 4 ppm A degrees C-1 in the 35-250 A degrees C temperature range. The conduction and relaxation phenomena were rationalized using universal AC conductivity power law and modulus formalism respectively. The activation energy for relaxation determined using imaginary parts of modulus peaks was 2.54 eV which was close to that of the DC conduction implying the involvement of similar energy barriers in both the processes. Stretched and power exponents were temperature dependent. The relaxation and conduction in these glasses were attributed to the hoping and migration of Bi3+ cations in their own and different local environment.

Mining sentiments from songs using latent dirichlet allocation

Song-selection and mood are interdependent. If we capture a song’s sentiment, we can determine the mood of the listener, which can serve as a basis for recommendation systems. Songs are generally classified according to genres, which don’t entirely reflect sentiments. Thus, we require an unsupervised scheme to mine them. Sentiments are classified into either two (positive/negative) or multiple (happy/angry/sad/...) classes, depending on the application. We are interested in analyzing the feelings invoked by a song, involving multi-class sentiments. To mine the hidden sentimental structure behind a song, in terms of “topics”, we consider its lyrics and use Latent Dirichlet Allocation (LDA). Each song is a mixture of moods. Topics mined by LDA can represent moods. Thus we get a scheme of collecting similar-mood songs. For validation, we use a dataset of songs containing 6 moods annotated by users of a particular website.

On improving the generalization of SVM classifier

The generalization performance of the SVM classifier depends mainly on the VC dimension and the dimensionality of the data. By reducing the VC dimension of the SVM classifier, its generalization performance is expected to increase. In the present paper, we argue that the VC dimension of SVM classifier can be reduced by applying bootstrapping and dimensionality reduction techniques. Experimental results showed that bootstrapping the original data and bootstrapping the projected (dimensionally reduced) data improved the performance of the SVM classifier.

Reuse, recycle to de-bloat software

Most Java programmers would agree that Java is a language that promotes a philosophy of “create and go forth”. By design, temporary objects are meant to be created on the heap, possibly used and then abandoned to be collected by the garbage collector. Excessive generation of temporary objects is termed “object churn” and is a form of software bloat that often leads to performance and memory problems. To mitigate this problem, many compiler optimizations aim at identifying objects that may be allocated on the stack. However, most such optimizations miss large opportunities for memory reuse when dealing with objects inside loops or when dealing with container objects. In this paper, we describe a novel algorithm that detects bloat caused by the creation of temporary container and String objects within a loop. Our analysis determines which objects created within a loop can be reused. Then we describe a source-to-source transformation that efficiently reuses such objects. Empirical evaluation indicates that our solution can reduce upto 40% of temporary object allocations in large programs, resulting in a performance improvement that can be as high as a 20% reduction in the run time, specifically when a program has a high churn rate or when the program is memory intensive and needs to run the GC often.

Smoothed functional and Quasi-Newton algorithms for routing in multi-stage queueing network with constraints

We consider the problem of optimal routing in a multi-stage network of queues with constraints on queue lengths. We develop three algorithms for probabilistic routing for this problem using only the total end-to-end delays. These algorithms use the smoothed functional (SF) approach to optimize the routing probabilities. In our model all the queues are assumed to have constraints on the average queue length. We also propose a novel quasi-Newton based SF algorithm. Policies like Join Shortest Queue or Least Work Left work only for unconstrained routing. Besides assuming knowledge of the queue length at all the queues. If the only information available is the expected end-to-end delay as with our case such policies cannot be used. We also give simulation results showing the performance of the SF algorithms for this problem.