Static analysis for checking data format compatibility of programs

Large software systems are developed by composing multiple programs. If the programs manip-ulate and exchange complex data, such as network packets or files, it is essential to establish that they follow compatible data formats. Most of the complexity of data formats is associated with the headers. In this paper, we address compatibility of programs operating over headers of network packets, files, images, etc. As format specifications are rarely available, we infer the format associated with headers by a program as a set of guarded layouts. In terms of these formats, we define and check compatibility of (a) producer-consumer programs and (b) different versions of producer (or consumer) programs. A compatible producer-consumer pair is free of type mismatches and logical incompatibilities such as the consumer rejecting valid outputs gen-erated by the producer. A backward compatible producer (resp. consumer) is guaranteed to be compatible with consumers (resp. producers) that were compatible with its older version. With our prototype tool, we identified 5 known bugs and 1 potential bug in (a) sender-receiver modules of Linux network drivers of 3 vendors and (b) different versions of a TIFF image library.

Analysis of a Genomic DNA Expression Library of Mycobacterium tuberculosis Using Tuberculosis Patient Sera: Evidence for Modulation of Host Immune Response

DNA obtained from a human sputum isolate of Mycobacterium tuberculosis, NTI-64719, which showed extensive dissemination in the guinea pig model resulting in a high score for virulence was used to construct an expression library in the lambda ZAP vector. The size of DNA inserts in the library ranged from 1 to 3 kb, and recombinants represented 60% of the total plaques obtained. When probed with pooled serum from chronically infected tuberculosis patients, the library yielded 176 recombinants with a range of signal intensities. Among these, 93 recombinants were classified into 12 groups on the basis of DNA hybridization experiments, The polypeptides synthesized by the recombinants were predominantly LacZ fusion proteins, Serum obtained from patients who were clinically diagnosed to be in the early phase of M. tuberculosis infection was used to probe the 176 recombinants obtained. interestingly, some recombinants that gave very strong signals in the original screen did not react with early-phase serum; conversely, others whose signals were extremely weak in the original screen gave very intense signals with serum from recently infected patients, This indicates the differential nature of either the expression of these antigens or the immune response elicited by them as a function of disease progression.

A measure of logical complexity of programs

The research in software science has so far been concentrated on three measures of program complexity: (a) software effort; (b) cyclomatic complexity; and (c) program knots. In this paper we propose a measure of the logical complexity of programs in terms of the variable dependency of sequence of computations, inductive effort in writing loops and complexity of data structures. The proposed complexity mensure is described with the aid of a graph which exhibits diagrammatically the dependence of a computation at a node upon the computation of other (earlier) nodes. Complexity measures of several example programs have been computed and the related issues have been discussed. The paper also describes the role played by data structures in deciding the program complexity.

Synergistic Execution of Stream Programs on Multicores with Accelerators

The StreamIt programming model has been proposed to exploit parallelism in streaming applications oil general purpose multicore architectures. The StreamIt graphs describe task, data and pipeline parallelism which can be exploited on accelerators such as Graphics Processing Units (GPUs) or CellBE which support abundant parallelism in hardware. In this paper, we describe a novel method to orchestrate the execution of if StreamIt program oil a multicore platform equipped with an accelerator. The proposed approach identifies, using profiling, the relative benefits of executing a task oil the superscalar CPU cores and the accelerator. We formulate the problem of partitioning the work between the CPU cores and the GPU, taking into account the latencies for data transfers and the required buffer layout transformations associated with the partitioning, as all integrated Integer Linear Program (ILP) which can then be solved by an ILP solver. We also propose an efficient heuristic algorithm for the work-partitioning between the CPU and the GPU, which provides solutions which are within 9.05% of the optimal solution on an average across the benchmark Suite. The partitioned tasks are then software pipelined to execute oil the multiple CPU cores and the Streaming Multiprocessors (SMs) of the GPU. The software pipelining algorithm orchestrates the execution between CPU cores and the GPU by emitting the code for the CPU and the GPU, and the code for the required data transfers. Our experiments on a platform with 8 CPU cores and a GeForce 8800 GTS 512 GPU show a geometric mean speedup of 6.94X with it maximum of 51.96X over it single threaded CPU execution across the StreamIt benchmarks. This is a 18.9% improvement over it partitioning strategy that maps only the filters that cannot be executed oil the GPU - the filters with state that is persistent across firings - onto the CPU.

Software Pipelined Execution of Stream Programs on GPUs

The StreamIt programming model has been proposed to exploit parallelism in streaming applications on general purpose multi-core architectures. This model allows programmers to specify the structure of a program as a set of filters that act upon data, and a set of communication channels between them. The StreamIt graphs describe task, data and pipeline parallelism which can be exploited on modern Graphics Processing Units (GPUs), as they support abundant parallelism in hardware. In this paper, we describe the challenges in mapping StreamIt to GPUs and propose an efficient technique to software pipeline the execution of stream programs on GPUs. We formulate this problem - both scheduling and assignment of filters to processors - as an efficient Integer Linear Program (ILP), which is then solved using ILP solvers. We also describe a novel buffer layout technique for GPUs which facilitates exploiting the high memory bandwidth available in GPUs. The proposed scheduling utilizes both the scalar units in GPU, to exploit data parallelism, and multiprocessors, to exploit task and pipelin parallelism. Further it takes into consideration the synchronization and bandwidth limitations of GPUs, and yields speedups between 1.87X and 36.83X over a single threaded CPU.

Identification and characterization of a library of microheterogeneous cyclohexadepsipeptides from the fungus Isaria

Ten new cyclic hexadepsipeptides, six isariins and four isaridins, from the fungus Isaria have been identified and characterized by high-performance liquid chromatography, coupled to tandem electrospray ionization mass spectrometry (LC-ESIMS/MS). The isariins possess a beta-hydroxy acid residue and five alpha-amino acids, while isaridins contain a beta-amino acid, an alpha-hydroxy acid, and four alpha-amino acids. One- and two-dimensional NMR spectroscopy confirmed the chemical identity of some of the isariin fractions. Mass spectral fragmentation patterns of [M + H](+) ions reveal clear diagnostic fragment ions for the isariins and isaridins. Previously described cyclic depsipeptides, isarfelins from Isaria felina (Guo, Y. X.; Liu, Q. H.; Ng, T. B.; Wang H. X. Peptides 2005, 26, 2384), are now reassigned as members of the isaridin family. Examination of isaridin sequences revealed significant similarities with cyclic hexadepsipeptides such as destruxins and roseotoxins. The structure of an isariin (isariin A) investigated by NMR spectroscopy indicated the presence of a hybrid alpha beta C-11 turn, formed by the beta-hydroxy acid and glycine residues and a (D)Leu-(L)Ala type II' beta-turn. Additionally, the inhibitory effect of isariins and an isaridin on the intra-erythrocytic growth of Plasmodium falciparum is presented.

Identification and characterization of a library of microheterogeneous cyclohexa-depsipeptides from the fungus

Ten new cyclic hexadepsipeptides, six isariins and four isaridins, from the fungus Isaria have been identified and characterized by high-performance liquid chromatography, coupled to tandem electrospray ionization mass spectrometry (LC-ESIMS/MS). The isariins possess a beta-hydroxy acid residue and five alpha-amino acids, while isaridins contain a beta-amino acid, an alpha-hydroxy acid, and four alpha-amino acids. One- and two-dimensional NMR spectroscopy confirmed the chemical identity of some of the isariin fractions. Mass spectral fragmentation patterns of [M + H](+) ions reveal clear diagnostic fragment ions for the isariins and isaridins. Previously described cyclic depsipeptides, isarfelins from Isaria felina (Guo, Y. X.; Liu, Q. H.; Ng, T. B.; Wang H. X. Peptides 2005, 26, 2384), are now reassigned as members of the isaridin family. Examination of isaridin sequences revealed significant similarities with cyclic hexadepsipeptides such as destruxins and roseotoxins. The structure of an isariin (isariin A) investigated by NMR spectroscopy indicated the presence of a hybrid alpha beta C-11 turn, formed by the beta-hydroxy acid and glycine residues and a (D)Leu-(L)Ala type II' beta-turn. Additionally, the inhibitory effect of isariins and an isaridin on the intra-erythrocytic growth of Plasmodium falciparum is presented.

Development of a structured program for conversion to prenex normal form

The method of structured programming or program development using a top-down, stepwise refinement technique provides a systematic approach for the development of programs of considerable complexity. The aim of this paper is to present the philosophy of structured programming through a case study of a nonnumeric programming task. The problem of converting a well-formed formula in first-order logic into prenex normal form is considered. The program has been coded in the programming language PASCAL and implemented on a DEC-10 system. The program has about 500 lines of code and comprises 11 procedures.

A note on resolving infeasibility in linear programs by constraint relaxation

We study the problem of finding a set of constraints of minimum cardinality which when relaxed in an infeasible linear program, make it feasible. We show the problem is NP-hard even when the constraint matrix is totally unimodular and prove polynomial-time solvability when the constraint matrix and the right-hand-side together form a totally unimodular matrix.

Definitions and nomenclature of nucleic acid structure parameters

At an EMBO Workshop on DNA Curvature and Bending, held at Churchill College, Cambridge, on 10-15 September 1988, two sessions were scheduled on definitions of parameters used to describe the geometry of nucleic acid chains and helices, and a common nomenclature for these parameters. The most widely used library of helix analysis programs, HELIB (Fratini et al., 1982; Dickerson, 1985) suffers from the fact that the translations and rotations as defined are not fully independent and depend to a certain extent upon the choice of overall helix axis. Several research groups have been engaged independently in developing alternative programs for the geometrical analysis of polynucleotide chains, but with different definitions of quantities calculated and with widely different nomenclature even when the same parameter was involved.

Forest policies and programs affecting vulnerability and adaptation to climate change

Due to large scale afforestation programs and forest conservation legislations, India's total forest area seems to have stabilized or even increased. In spite of such efforts, forest fragmentation and degradation continues, with forests being subject to increased pressure due to anthropogenic factors. Such fragmentation and degradation is leading to the forest cover to change from very dense to moderately dense and open forest and 253 km(2) of very dense forest has been converted to moderately dense forest, open forest, scrub and non-forest (during 2005-2007). Similarly, there has been a degradation of 4,120 km(2) of moderately dense forest to open forest, scrub and non-forest resulting in a net loss of 936 km(2) of moderately dense forest. Additionally, 4,335 km(2) of open forest have degraded to scrub and non-forest. Coupled with pressure due to anthropogenic factors, climate change is likely to be an added stress on forests. Forest sector programs and policies are major factors that determine the status of forests and potentially resilience to projected impacts of climate change. An attempt is made to review the forest policies and programs and their implications for the status of forests and for vulnerability of forests to projected climate change. The study concludes that forest conservation and development policies and programs need to be oriented to incorporate climate change impacts, vulnerability and adaptation.

Intracellular Pathogen Sensor NOD2 Programs Macrophages to Trigger Notch1 Activation

Intracellular pathogen sensor, NOD2, has been implicated in regulation of wide range of anti-inflammatory responses critical during development of a diverse array of inflammatory diseases; however, underlying molecular details are still imprecisely understood. In this study, we demonstrate that NOD2 programs macrophages to trigger Notch1 signaling. Signaling perturbations or genetic approaches suggest signaling integration through cross-talk between Notch1-PI3K during the NOD2-triggered expression of a multitude of immunological parameters including COX-2/PGE(2) and IL-10. NOD2 stimulation enhanced active recruitment of CSL/RBP-Jk on the COX-2 promoter in vivo. Intriguingly, nitric oxide assumes critical importance in NOD2-mediated activation of Notch1 signaling as iNOS(-/-) macrophages exhibited compromised ability to execute NOD2-triggered Notch1 signaling responses. Correlative evidence demonstrates that this mechanism operates in vivo in brain and splenocytes derived from wild type, but not from iNOS(-/-) mice. Importantly, NOD2-driven activation of the Notch1-PI3K signaling axis contributes to its capacity to impart survival of macrophages against TNF-alpha or IFN-gamma-mediated apoptosis and resolution of inflammation. Current investigation identifies Notch1-PI3K as signaling cohorts involved in the NOD2-triggered expression of a battery of genes associated with anti-inflammatory functions. These findings serve as a paradigm to understand the pathogenesis of NOD2-associated inflammatory diseases and clearly pave a way toward development of novel therapeutics.

Tool for Identification of Duplicate Records Downloaded from Multiple Cd-Roms. A Case Study with Spirs Based Databases

As research becomes more and more interdisciplinary, literature search from CD-ROM databases is often carried out on more than one CD-ROM database. This results in retrieving duplicate records due to same literature being covered (indexed) in more than one database. The retrieval software does not identify such duplicate records. Three different programs have been written to accomplish the task of identifying the duplicate records. These programs are executed from a shell script to minimize manual intervention. The various fields that have been used (extracted) to identify the duplicate records include the article title, year, volume number, issue number and pagination. The shell script when executed prompts for input file that may contain duplicate records. The programs identify the duplicate records and write them to a new file.

Integrating CDS/ISIS Databases with Greenstone Digital Library Software (GSDL)

CDS/ISIS is an advanced non-numerical information storage and retrieval software developed by UNESCO since 1985 to satisfy the need expressed by many institutions, especially in developing countries, to be able to streamline their information processing activities by using modern (and relatively inexpensive) technologies [1]. CDS/ISIS is available for MS-DOS, Windows and Unix operating system platforms. The formatting language of CDS/ISIS is one of its several strengths. It is not only used for formatting records for display but is also used for creating customized indexes. CDS/ISIS by itself does not facilitate in publishing its databases on the Internet nor does it facilitate in publishing on CD-ROMs. However, numbers of open source tools are now available, which enables in publishing CDS/ISIS databases on the Internet and also on CD-ROMs. In this paper, we have discussed the ways and means of integrating CDS/ISIS databases with GSDL, an open source digital library (DL) software.

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.