Minimizing buffer requirements under rate-optimal schedule in regular dataflow networks

Large-grain synchronous dataflow graphs or multi-rate graphs have the distinct feature that the nodes of the dataflow graph fire at different rates. Such multi-rate large-grain dataflow graphs have been widely regarded as a powerful programming model for DSP applications. In this paper we propose a method to minimize buffer storage requirement in constructing rate-optimal compile-time (MBRO) schedules for multi-rate dataflow graphs. We demonstrate that the constraints to minimize buffer storage while executing at the optimal computation rate (i.e. the maximum possible computation rate without storage constraints) can be formulated as a unified linear programming problem in our framework. A novel feature of our method is that in constructing the rate-optimal schedule, it directly minimizes the memory requirement by choosing the schedule time of nodes appropriately. Lastly, a new circular-arc interval graph coloring algorithm has been proposed to further reduce the memory requirement by allowing buffer sharing among the arcs of the multi-rate dataflow graph. We have constructed an experimental testbed which implements our MBRO scheduling algorithm as well as (i) the widely used periodic admissible parallel schedules (also known as block schedules) proposed by Lee and Messerschmitt (IEEE Transactions on Computers, vol. 36, no. 1, 1987, pp. 24-35), (ii) the optimal scheduling buffer allocation (OSBA) algorithm of Ning and Gao (Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, SC, Jan. 10-13, 1993, pp. 29-42), and (iii) the multi-rate software pipelining (MRSP) algorithm (Govindarajan and Gao, in Proceedings of the 1993 International Conference on Application Specific Array Processors, Venice, Italy, Oct. 25-27, 1993, pp. 77-88). Schedules generated for a number of random dataflow graphs and for a set of DSP application programs using the different scheduling methods are compared. The experimental results have demonstrated a significant improvement (10-20%) in buffer requirements for the MBRO schedules compared to the schedules generated by the other three methods, without sacrificing the computation rate. The MBRO method also gives a 20% average improvement in computation rate compared to Lee's Block scheduling method.

Localisation of discrete change in a transformer winding: a network-function-loci approach

An entirely different approach for localisation of winding deformation based on terminal measurements is presented. Within the context of this study, winding deformation means, a discrete and specific change externally imposed at a particular position on the winding. The proposed method is based on pre-computing and plotting the complex network-function loci e.g. driving-point impedance (DPI)] at a selected frequency, for a meaningful range of values for each element (increasing and decreasing) of the ladder network which represents the winding. This loci diagram is called the nomogram. After introducing a discrete change, amplitude and phase of DPI are measured. By plotting this single measurement on the nomogram, it is possible to estimate the location and identify the extent of change. In contrast to the existing approach, the proposed method is fast, non-iterative and yields reasonably good localisation. Experimental results for actual transformer windings (interleaved and continuous disc) are presented.

PL due to Discrete Gap Levels in Some Chalcogenide Glasses- A Configurational Coordinate Diagram Illustration

Photoluminescence (PL) studies were carried out on a-Se and a few Ge20Se80−xBix and Ge20Se70−xBixTe10 bulk glassy semiconductors at 4.2 K with Ar+ laser as excitation source. While a-Se and samples with lesser at% of Bi show fine structured PL with a large Stokes shift, samples with higher at% of Bi did not show any detectable PL. The investigations show at least three radiative recombination transitions. Features extracted by deconvoluting the experimental spectra show that the discrete gap levels associated with the inherent coordination defects are involved in the PL transitions. Absence of PL in samples with higher Bi at% are explained on the basis of nonradiative transition mechanisms. Overall PL mechanism involving gap levels in chalcogenide glasses is illustrated with the help of a configurational coordinate diagram.

Boxicity of Line Graphs

The boxicity of a graph H, denoted by View the MathML source, is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in View the MathML source. In this paper we show that for a line graph G of a multigraph, View the MathML source, where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, View the MathML source. For the d-dimensional hypercube Qd, we prove that View the MathML source. The question of finding a nontrivial lower bound for View the MathML source was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800]. The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).

Seismic Microzonation: Principles,Practices and Experiments

This paper presents an overview of the seismic microzonation and the grade/level based study along with methods used for estimating hazard. The principles of seismic microzonation along with some current practices are discussed. Summary of seismic microzonation experiments carried out in India is presented. A detailed work of seismic microzonation of Bangalore has been presented as a case study. In this case study, a seismotectonic map for microzonation area has been developed covering 350 km radius around Bangalore, India using seismicity and seismotectonic parameters of the region. For seismic microzonation Bangalore Mahanagar Palike (BMP) area of 220 km2 has been selected as the study area. Seismic hazard analysis has been carried out using deterministic as well as probabilistic approaches. Synthetic ground motion at 653 locations, recurrence relation and peak ground acceleration maps at rock level have been generated. A detailed site characterization has been carried out using borehole with standard penetration test (SPT) ―N‖ values and geophysical data. The base map and 3-dimensional sub surface borehole model has been generated for study area using geographical information system (GIS). Multichannel analysis of surface wave (MASW)method has been used to generate one-dimensional shear wave velocity profile at 58 locations and two- dimensional profile at 20 locations. These shear wave velocities are used to estimate equivalent shear wave velocity in the study area at every 5m intervals up to a depth of 30m. Because of wider variation in the rock depth, equivalent shear for the soil overburden thickness alone has been estimated and mapped using ArcGIS 9.2. Based on equivalent shear wave velocity of soil overburden thickness, the study area is classified as ―site class D‖. Site response study has been carried out using geotechnical properties and synthetic ground motions with program SHAKE2000.The soil in the study area is classified as soil with moderate amplification potential. Site response results obtained using standard penetration test (SPT) ―N‖ values and shear wave velocity are compared, it is found that the results based on shear wave velocity is lower than the results based on SPT ―N‖ values. Further, predominant frequency of soil column has been estimated based on ambient noise survey measurements using instruments of L4-3D short period sensors equipped with Reftek 24 bit digital acquisition systems. Predominant frequency obtained from site response study is compared with ambient noise survey. In general, predominant frequencies in the study area vary from 3Hz to 12Hz. Due to flat terrain in the study area, the induced effect of land slide possibility is considered to be remote. However, induced effect of liquefaction hazard has been estimated and mapped. Finally, by integrating the above hazard parameters two hazard index maps have been developed using Analytic Hierarchy Process (AHP) on GIS platform. One map is based on deterministic hazard analysis and other map is based on probabilistic hazard analysis. Finally, a general guideline is proposed by bringing out the advantages and disadvantages of different approaches.

Performance analysis of a fluid queue with random service rate in discrete time

We consider a fluid queue in discrete time with random service rate. Such a queue has been used in several recent studies on wireless networks where the packets can be arbitrarily fragmented. We provide conditions on finiteness of moments of stationary delay, its Laplace-Stieltjes transform and various approximations under heavy traffic. Results are extended to the case where the wireless link can transmit in only a few slots during a frame.