In this paper, we propose a novel set of techniques that allows multicore programmers and architects alike to rapidly estimate the availability of parallelism in their target programs. We present p-ray, which, given an application and the input, shows the nested relationship and availability of parallelism across different regions in complex programs, using a parallelism chart, or p-chart. P-ray also prioritizes the regions, suggesting the ordering that the programmer should attack them in, based on the estimated parallelism and the code complexity. P-ray can also estimate the kind of parallelism (TLP, DLP or ILP) that is found in each region, which allows the user to determine the available techniques are likely to work. In this paper, we show three case studies, including SpecInt's gzip, and Mat2C's capacitor, and Nasa7's Vpenta, and follow up with results which compare actual parallelization results of a benchmark suite against the results predicted by p-ray.

Pre-2018 CSE ID: CS2009-0950

The Muller F element (4.2 Mb, ~80 protein-coding genes) is an unusual autosome of Drosophila melanogaster; it is mostly heterochromatic with a low recombination rate. To investigate how these properties impact the evolution of repeats and genes, we manually improved the sequence and annotated the genes on the D. erecta, D. mojavensis, and D. grimshawi F elements and euchromatic domains from the Muller D element. We find that F elements have greater transposon density (25-50%) than euchromatic reference regions (3-11%). Among the F elements, D. grimshawi has the lowest transposon density (particularly DINE-1: 2% vs. 11-27%). F element genes have larger coding spans, more coding exons, larger introns, and lower codon bias. Comparison of the Effective Number of Codons with the Codon Adaptation Index shows that, in contrast to the other species, codon bias in D. grimshawi F element genes can be attributed primarily to selection instead of mutational biases, suggesting that density and types of transposons affect the degree of local heterochromatin formation. F element genes have lower estimated DNA melting temperatures than D element genes, potentially facilitating transcription through heterochromatin. Most F element genes (~90%) have remained on that element, but the F element has smaller syntenic blocks than genome averages (3.4-3.6 vs. 8.4-8.8 genes per block), indicating greater rates of inversion despite lower rates of recombination. Overall, the F element has maintained characteristics that are distinct from other autosomes in the Drosophila lineage, illuminating the constraints imposed by a heterochromatic milieu.