The complexity of certain incremental code generation problems

This paper looks at the complexity of four different incremental problems. The following are the problems considered: (1) Interval partitioning of a flow graph (2) Breadth first search (BFS) of a directed graph (3) Lexicographic depth first search (DFS) of a directed graph (4) Constructing the postorder listing of the nodes of a binary tree. The last problem arises out of the need for incrementally computing the Sethi-Ullman (SU) ordering [1] of the subtrees of a tree after it has undergone changes of a given type. These problems are among those that claimed our attention in the process of our designing algorithmic techniques for incremental code generation. BFS and DFS have certainly numerous other applications, but as far as our work is concerned, incremental code generation is the common thread linking these problems. The study of the complexity of these problems is done from two different perspectives. In [2] is given the theory of incremental relative lower bounds (IRLB). We use this theory to derive the IRLBs of the first three problems. Then we use the notion of a bounded incremental algorithm [4] to prove the unboundedness of the fourth problem with respect to the locally persistent model of computation. Possibly, the lower bound result for lexicographic DFS is the most interesting. In [5] the author considers lexicographic DFS to be a problem for which the incremental version may require the recomputation of the entire solution from scratch. In that sense, our IRLB result provides further evidence for this possibility with the proviso that the incremental DFS algorithms considered be ones that do not require too much of preprocessing.

On the achievable rates of sources having a group alphabet in a distributed source coding setting

We consider the problem of compression via homomorphic encoding of a source having a group alphabet. This is motivated by the problem of distributed function computation, where it is known that if one is only interested in computing a function of several sources, then one can at times improve upon the compression rate required by the Slepian-Wolf bound. The functions of interest are those which could be represented by the binary operation in the group. We first consider the case when the source alphabet is the cyclic Abelian group, Zpr. In this scenario, we show that the set of achievable rates provided by Krithivasan and Pradhan [1], is indeed the best possible. In addition to that, we provide a simpler proof of their achievability result. In the case of a general Abelian group, an improved achievable rate region is presented than what was obtained by Krithivasan and Pradhan. We then consider the case when the source alphabet is a non-Abelian group. We show that if all the source symbols have non-zero probability and the center of the group is trivial, then it is impossible to compress such a source if one employs a homomorphic encoder. Finally, we present certain non-homomorphic encoders, which also are suitable in the context of function computation over non-Abelian group sources and provide rate regions achieved by these encoders.

Network Error Correction for Unit-Delay, Memory-Free Networks Using Convolutional Codes

A single source network is said to be memory-free if all of the internal nodes (those except the source and the sinks) do not employ memory but merely send linear combinations of the symbols received at their incoming edges on their outgoing edges. In this work, we introduce network-error correction for single source, acyclic, unit-delay, memory-free networks with coherent network coding for multicast. A convolutional code is designed at the source based on the network code in order to correct network- errors that correspond to any of a given set of error patterns, as long as consecutive errors are separated by a certain interval which depends on the convolutional code selected. Bounds on this interval and the field size required for constructing the convolutional code with the required free distance are also obtained. We illustrate the performance of convolutional network error correcting codes (CNECCs) designed for the unit-delay networks using simulations of CNECCs on an example network under a probabilistic error model.

Inhibition of hepatitis C virus replication by herbal extract: Phyllanthus amarus as potent natural source

Hepatitis C virus infection is a major health problem worldwide. Developing effective antiviral therapy for HCV is the need of the hour. The viral enzymes NS3 protease and NS5B RNA dependent RNA polymerase are essential enzymes for polyprotein processing and viral RNA replication and thus can be potential targets for screening anti-HCV compounds. A large number of phytochemicals are present in plants, which are found to be promising antiviral agents. In this study, we have screened inhibitory effect of different plant extracts against the NS3 and NS5B enzymes of hepatitis C virus. Methanolic extracts were prepared from various plant materials and their inhibitory effects on the viral enzymes were determined by in vitro enzyme assays. Effect on viral RNA replication was investigated by using TaqMan Real time RT-PCR. Interestingly, Phyllanthus amarus root (PAR) extract showed significant inhibition of HCV-NS3 protease enzyme; whereas P. amarus leaf (PAL) extract showed considerable inhibition of NS5B in the in vitro assays. Further, the PAR and PAL extracts significantly inhibited replication of HCV monocistronic replicon RNA and HCV H77S viral RNA in HCV cell culture system. However, both PAR and PAL extracts did not show cytotoxicity in Huh7 cells in the MTT assay. Furthermore, addition of PAR together with IFN-alpha showed additive effect in the inhibition of HCV RNA replication. Results suggest the possible molecular basis of the inhibitory activity of PA extract against HCV which would help in optimization and subsequent development of specific antiviral agent using P. amarus as potent natural source. (C) 2011 Elsevier B.V. All rights reserved.

Discovery of Application Workloads from Network File Traces

An understanding of application I/O access patterns is useful in several situations. First, gaining insight into what applications are doing with their data at a semantic level helps in designing efficient storage systems. Second, it helps create benchmarks that mimic realistic application behavior closely. Third, it enables autonomic systems as the information obtained can be used to adapt the system in a closed loop.All these use cases require the ability to extract the application-level semantics of I/O operations. Methods such as modifying application code to associate I/O operations with semantic tags are intrusive. It is well known that network file system traces are an important source of information that can be obtained non-intrusively and analyzed either online or offline. These traces are a sequence of primitive file system operations and their parameters. Simple counting, statistical analysis or deterministic search techniques are inadequate for discovering application-level semantics in the general case, because of the inherent variation and noise in realistic traces.In this paper, we describe a trace analysis methodology based on Profile Hidden Markov Models. We show that the methodology has powerful discriminatory capabilities that enable it to recognize applications based on the patterns in the traces, and to mark out regions in a long trace that encapsulate sets of primitive operations that represent higher-level application actions. It is robust enough that it can work around discrepancies between training and target traces such as in length and interleaving with other operations. We demonstrate the feasibility of recognizing patterns based on a small sampling of the trace, enabling faster trace analysis. Preliminary experiments show that the method is capable of learning accurate profile models on live traces in an online setting. We present a detailed evaluation of this methodology in a UNIX environment using NFS traces of selected commonly used applications such as compilations as well as on industrial strength benchmarks such as TPC-C and Postmark, and discuss its capabilities and limitations in the context of the use cases mentioned above.

Dynamic path profile aided recompilation in a JAVA just-in-time compiler

Just-in-Time (JIT) compilers for Java can be augmented by making use of runtime profile information to produce better quality code and hence achieve higher performance. In a JIT compilation environment, the profile information obtained can be readily exploited in the same run to aid recompilation and optimization of frequently executed (hot) methods. This paper discusses a low overhead path profiling scheme for dynamically profiling AT produced native code. The profile information is used in recompilation during a subsequent invocation of the hot method. During recompilation tree regions along the hot paths are enlarged and instruction scheduling at the superblock level is performed. We have used the open source LaTTe AT compiler framework for our implementation. Our results on a SPARC platform for SPEC JVM98 benchmarks indicate that (i) there is a significant reduction in the number of tree regions along the hot paths, and (ii) profile aided recompilation in LaTTe achieves performance comparable to that of adaptive LaTTe in spite of retranslation and profiling overheads.

On using peak amplitude and rise time for AE source characterization

Acoustic Emission (AE) signals, which are electrical version of acoustic emissions, are usually analysed using a set of signal parameters. The major objective of signal analysis is to study the characteristics of the sources of emissions. Peak amplitude (P-a) and rise time (R-t) are two such parameters used for source characterization. In this paper, we theoretically investigate the efficiency of P-a and R-t to classify and characterize AE sources by modelling the input stress pulse and transducer. Analytical expressions obtained for P-a and R-t clearly indicate their use and efficiency for source characterization. It is believed that these results may be of use to investigators in areas like control systems and signal processing also.

Photoelectron spectroscopy beamline on Indus-1 synchrotron radiation source

We describe here a photoelectron spectroscopy beamline installed on Indus-1 storage ring. Initially we give a brief description of optical and mechanical layout of beam-line. The beamline optics was designed to cover energy range from 10 eV to 200 eV and it consists of a pre-focusing mirror, a toroidal grating monochromator and a post-focusing mirror. We then discuss indigenously developed ultra high vacuum compatible work station to carry out angle integrated photoemission experiments. The beamline has been successfully commissioned and photoemission measurements on a variety of standard samples are presented.

Techniques for realistic visualization of fluids: A survey

Visualization of fluids has wide applications in science, engineering and entertainment. Various methodologies Of visualizing fluids have evolved which emphasize on capturing different aspects of the fluids accurately. In this survey the existing methods for realistic visualization of fluids are reviewed. The approaches are classified based on the key concept they rely on for fluid modeling. This classification allows for easy selection of the method to be adopted for visualization given an application. It also enables identification of alternative techniques for fluid modeling.

Starting scheme for load commutated inverter-fed wound field synchronous machine using an auxiliary low-power voltage source inverter

Conventional thyristor-based load commutated inverter (LCI)-fed wound field synchronous machine operates only above a minimum speed that is necessary to develop enough back emf to ensure commutation. The drive is started and brought up to a speed of around 10-15% by a complex `dc link current pulsing' technique. During this process, the drive have problems such as pulsating torque, insufficient average starting torque, longer starting time, etc. In this regard a simple starting and low-speed operation scheme, by employing an auxiliary low-power voltage source inverter (VSI) between the LCI and the machine terminals, is presented in this study. The drive is started and brought up to a low speed of around 15% using the VSI alone with field oriented control. The complete control is then smoothly and dynamically transferred to the conventional LCI control. After the control transfer, the VSI is turned off and physically disconnected from the main circuit. The advantages of this scheme are smooth starting, complete control of torque and flux at starting and low speeds, less starting time, stable operation, etc. The voltage rating of the required VSI is very low of the order of 10-15%, whereas the current rating is dependent on the starting torque requirement of the load. The experimental results from a 15.8 hp LCI-fed wound field synchronous machine are given to demonstrate the scheme.

Efficient statistical modeling for the compression of tree structured intermediate code

We propose a scheme for the compression of tree structured intermediate code consisting of a sequence of trees specified by a regular tree grammar. The scheme is based on arithmetic coding, and the model that works in conjunction with the coder is automatically generated from the syntactical specification of the tree language. Experiments on data sets consisting of intermediate code trees yield compression ratios ranging from 2.5 to 8, for file sizes ranging from 167 bytes to 1 megabyte.

On the Compressibility of non-Abelian-Group Sources in a Distributed Source Coding Setting

We consider the problem of compression of a non-Abelian source.This is motivated by the problem of distributed function computation,where it is known that if one is only interested in computing a function of several sources, then one can often improve upon the compression rate required by the Slepian-Wolf bound. Let G be a non-Abelian group having center Z(G). We show here that it is impossible to compress a source with symbols drawn from G when Z(G) is trivial if one employs a homomorphic encoder and a typical-set decoder.We provide achievable upper bounds on the minimum rate required to compress a non-Abelian group with non-trivial center. Also, in a two source setting, we provide achievable upper bounds for compression of any non-Abelian group, using a non-homomorphic encoder.

A Low-Complexity, Full-Rate, Full-Diversity 2x2 STBC with Golden Code's Coding Gain

This paper presents a low-ML-decoding-complexity, full-rate, full-diversity space-time block code (STBC) for a 2 transmit antenna, 2 receive antenna multiple-input multipleoutput (MIMO) system, with coding gain equal to that of the best and well known Golden code for any QAM constellation.Recently, two codes have been proposed (by Paredes, Gershman and Alkhansari and by Sezginer and Sari), which enjoy a lower decoding complexity relative to the Golden code, but have lesser coding gain. The 2 × 2 STBC presented in this paper has lesser decoding complexity for non-square QAM constellations,compared with that of the Golden code, while having the same decoding complexity for square QAM constellations. Compared with the Paredes-Gershman-Alkhansari and Sezginer-Sari codes, the proposed code has the same decoding complexity for nonrectangular QAM constellations. Simulation results, which compare the codeword error rate (CER) performance, are presented.

Performance analysis of wavelength/time codes with and without hard-limiter

Fiber-optic CDMA technology is well suited for high speed local-area-networks (LANs) as it has good salient features. In this paper, we model the wavelength/time multiple-pulses-per-row (W/T MPR) FO-CDMA network channel, as a Z channel. We compare the performances of W/T MPR code with and without hard-limiter and show that significant performance improvement can be achieved by using hard-limiters in the receivers. In broadcast channels, MAI is the dominant source of noise. Hence the performance analysis is carried out considering only MAI and other receiver noises are neglected.