dataesr/scientific-paragraphs-categorization huggingface dataset:
However, we show that it is possible to discover high quality schedules using stochastic search. Given a schedule, our compiler automatically synthesizes high quality parallel vector code for x86 and ARM CPUs with SSE/AVX and NEON, and graphs of CUDA kernels interwoven with host management code for hybrid GPU execution. It automatically infers all internal allocations and a complete loop nest using simple but general interval analysis  [18]. Directly mapping data parallel dimensions to SIMD execution, including careful treatment of strided access patterns, enables high quality vector code generation, without requiring any general-purpose loop auto-vectorization. The end result is a system which enables terse, composable programs to achieve state-of-the-art performance on a wide range of real image processing pipelines, and across different hardware architectures, including multicores with SIMD, and heterogeneous CPU+GPU execution.
The Halide DSL We use the Halide DSL to describe image processing pipelines in a simple functional style  [26]. A simple C++ implementation of local Laplacian filters (Fig. 1 ) is described by dozens of loop nests and hundreds of lines of code. This is not practical to globally optimize with traditional loop optimization systems. The Halide version distills this into 62 lines describing just the essential dataflow and computation in the 99 stage pipeline, and all choices for how the program should be synthesized are described separately (Sec. 3). In Halide, values that would be mutable arrays in an imperative language are instead functions from coordinates to values. It represents images as pure functions defined over an infinite integer domain, where the value of a function at a point represents the color of the corresponding pixel.
Our model considers only axis-aligned bounding regions, not general polytopes-a practical simplification for image processing and many other applications. But this also allows the regions to be defined and analyzed using simple interval analysis. Since our model of scheduling relies on later compiler inference to determine the bounds of evaluation and storage for each function and loop, it is essential that bounds analysis be capable of analyzing every expression and construct in the Halide language. Interval analysis is simpler than modern tools like polyhedral analysis, but it can effectively analyze through a wider range of expressions, which is essential for this design. The Call Schedule In addition to the order of evaluation within the domain of each function, the schedule also specifies the granularity of interleaving the computation of a function with the storage and computation of each function on which it depends.
Compiling Scheduled Pipelines Our compiler combines the functions describing a Halide pipeline, with a fully-specified schedule for each function, to synthesize the machine code for a single procedure which implements the entire pipeline. The generated pipeline is exposed as a C ABI callable function which takes buffer pointers for input and output data, as well as scalar parameters. The implementation is multithreaded and vectorized according to the schedule, internally manages the allocation of all intermediate storage, and optionally includes synthesized GPU kernels which it also manages automatically. The compiler makes no heuristic decisions about which loop transformations to apply or what will generate fast code. For all such questions we defer to the schedule. At the same time, the generated code is safe by construction.
This code takes the form of a loop nest constructed using the domain order of the callee. The allocation for the callee is similarly injected at some containing loop level specified by the schedule. In Fig. 5 , middle, blurx is allocated at the level of tiles (out. xo), while it is computed as required for each scanline within the tile. Our compiler is driven by an autotuner, which stochastically searches the space of valid schedules to find a high performance implementation of the given Halide program. The core of the compiler lowers a functional representation of an imaging pipeline to imperative code using a schedule. It does this by first constructing a loop nest producing the final stage of the pipeline (in this case out), and then recursively injecting the storage and computation of earlier stages of the pipeline at the loop levels specified by the schedule.
The locations and sizes of regions computed are symbolic at this point. They are resolved by the subsequent bound inference pass, which injects interval arithmetic computations in a preamble at each loop level that set the region produced of each stage to be at least as large as the region consumed by subsequent stages. Next, sliding window optimization and storage folding remove redundant computation and excess storage where the storage granularity is above the compute granularity. A simple flattening transform converts multidimensional coordinates in the infinite domain of each function into simple one-dimensional indices relative to the base of the corresponding buffer. Vectorization and unrolling passes replace loops of constant with k scheduled as vectorized or unrolled with the corresponding k-wide vector code or k copies of the loop body.
They are defined by expressions which compute concrete bounds as a preamble at each loop level (e. g. , in Fig. 5 , right, the minimum bound of blurx. y is computed from interval analysis of the index expressions at which it is accessed combined with the bounds of the calling function, out). In practice, hoisting dynamic bounds evaluation expressions to the outermost loop level possible makes the runtime overhead of more complex bounds expressions negligible. Interval analysis is an unusual choice in a modern loop synthesis and code generation system. The resulting min/max bounds for each dimension are less expressive than the polyhedral model. They can only describe iteration over axis-aligned boxes, rather than arbitrary polytopes. However, it is trivial to synthesize efficient loops for any set of intervals, in contrast to the problem of scanning general polyhedra.
All of our IR nodes are meaningful for vector types: loads become gathers, stores become scatters, arithmetic becomes vector arithmetic, ternary expressions become vector selects, and so on. Later, during code generation, loads and stores of a linear expression of k * ramp(n)+o will become dense vector loads and stores if the coefficient k = 1, or strided loads and stores with stride k otherwise. In contrast to many languages, Halide has no divergent control flow, so this transformation is always well-defined and straight-forward to apply. In our representation, we never split a vector into a bundle of scalars. It is always a single expression containing ramps and broadcast nodes. We have found that this yields extremely efficient code without any sort of generalized loop auto-vectorization.
Back-end Code Generation Finally, we perform low-level optimizations and emit machine code for the resulting pipeline. Our primary backends use LLVM for lowlevel code generation. We first run a standard constant-folding and dead-code elimination pass on our IR, which also performs symbolic simplification of common patterns produced by bounds inference. At this point, the representation is ready to be lowered to LLVM IR. There is mostly a one-to-one mapping between our representation and LLVM's, but two specific patterns warrant mention. First, parallel for loops are lowered to LLVM code that first builds a closure containing state referred to in the body of a for loop. The loop body is lowered to a separate function that accepts the closure as an argument and performs one iteration of the loop.
We finally generate code that enqueues the iterations of the loop onto a task queue, which a thread pool consumes at runtime. Second, many vector patterns are difficult to express or generate poor code if passed directly to LLVM. We use peephole optimization to reroute these to architecture-specific intrinsics. For example, we perform our own analysis pass to determine alignment of vector loads and stores, and we catch common patterns such as interleaving stores, strided loads, vector averages, clamped arithmetic, fixedpoint arithmetic, widening or narrowing arithmetic, etc. By mapping specific expression IR patterns to specific SIMD opcodes on each architecture, we provide a means for the programmer to make use of all relevant SIMD operations on ARM (using NEON) and x86 (using SSE and AVX).
Additionally, the extent of the thread loops must fit within the corresponding limits of the target device. Other than that, all the standard looping constructs may still be scheduled outside or within the block and grid dimensions. This corresponds to loops which internally launch GPU kernels, and loops within each thread of a GPU kernel, respectively. Given a schedule annotated with GPU block and thread dimensions, our compiler proceeds exactly as before, synthesizing a single set of loop nests for the entire pipeline. No stage before the backend is aware of GPU execution; block and thread dimensions are treated like any other loops. The GPU backend extends the x86 backend, including its full feature set. Outside the loops over block and thread dimensions, the compiler generates the same optimized SSE code as it would in the pure CPU target.
At the start of each GPU block loop nest, we carve off the sub-nest much like a parallel for loop in the CPU backend, only it is spawned on the GPU. We first build a closure over all state which flows into the GPU loops. We then generate a GPU kernel from the body of those loops. And finally, we generate the host API calls to launch that kernel at the corresponding point in the host code, passing the closure as an argument. We also generate dynamic code before and after launches to track which buffers need to be copied to or from the device. Every allocated buffer which is used on the GPU has a corresponding device memory allocation, and their contents are lazily copied only when needed. The end result is not individual GPU kernels, but large graphs of hybrid CPU/GPU execution, described by the same scheduling model which drives the CPU backends.
Autotuning Pipeline Schedules We apply stochastic search to automatically find good schedules for Halide pipelines. The automatic optimizer takes a fixed algorithm and attempts to optimize the running time by searching for the most efficient schedule. The schedule search space is enormous-far too large to search exhaustively. For example in the local Laplacian filters pipeline, we estimate a lower bound of 10 720 schedules. This is derived by labeling functions with three tilings per function and all possible store and compute granularities. The actual dimensionality of the space is likely much higher. The optimal schedule dependends on machine architecture, image dimensions, and code generation in complex ways, and exhibits global dependencies between choices due to loop fusion and caching behavior.
Variable and block size arguments are randomized and chosen from small powers of two. Because schedules have complex global dependencies, not all schedules are valid: for example, a schedule could be computed or stored inside a dimension that does not exist in the caller's loop order. Genetic operations such as mutate and crossover may invalidate correct parent schedules. In general therefore we reject any partially completed schedules that are invalid, and continue sampling until we obtain valid schedules. We also verify the program output against a correct reference schedule, over several input images. This is just a sanity check: all valid schedules should generate correct code. Finally to prevent explosion of generated code due to complex pipelines, we limit the number of domain scheduling operations for each function.
This is a simple example of two consecutive stencils. Our reference comparison is a hand-optimized, manually fused and multithreaded loop nest defined entirely in SSE intrinsics  [26]. This version is 12× faster than a simple pair of loops in C compiled by GCC 4. 7. The version found by our autotuner is 10% faster, still, while being generated from a two line Halide algorithm rather than 35 lines of intrinsics. In some cases, the number of functions exceeds the number of program lines in Fig. 7 , because Halide functions are meta-programmed using higher-order functions. Camera pipeline transforms the raw data recorded by the camera sensor into a usable image. Its demosaicking, alone, is a complex combination of 21 interleaved and inter-dependent stencils. The reference comparison is a single carefully tiled and fused loop nest from the Frankencamera, expressed in 306 lines of C++  [1].
All producer-consumer communication is staged through scratch buffers, tiles are distributed over parallel threads using OpenMP, and the tight loops are autovectorized by GCC. The Halide algorithm is 145 lines describing 32 functions and 22 different stencils, literally translated from the pseudocode in the comments explaining the original source. It compiles to an implementation 3. 4× faster than the hand-tuned original. The autotuned schedule fuses long chains of stages through complex, interleaved stencils on overlapping tiles, fully fuses other stages, vectorizes every stage, and distributes blocks of scanlines across threads. Multi-scale interpolation uses an image pyramid to interpolate pixel data for seamless compositing. This requires dealing with data at many different resolutions.
The resulting pyramids are chains of stages which locally resample over small stencils, but through which dependence propagates globally across the entire image. The reference implementation is a carefully-structured set of loop nests which were hand-tuned by an Adobe engineer to generate a fully vectorized implementation in GCC. The Halide algorithm is substantially simpler, but compiles to an implementation 1. 7× faster than the original parallel vector code. The same Halide algorithm also automatically compiles to a graph of CUDA kernels and x86 code which is 5. 9× faster. Bilateral grid is an efficient implementation of the bilateral filter, which smoothes an image while preserving its main edges  [5, 21]. It first scatters the image data into a 3D grid, effectively building a windowed histogram in each column of the grid, then blurs the grid along each of is axes with three 5-point stencils.
Finally, the output image is constructed by trilinear interpolation within the grid at locations determined by the input image. The CPU reference code is a tuned but clean implementation from the original authors in 122 lines of C++. It is partially autovectorized by GCC, but is nontrivial to multithread (a naive OpenMP parallelization of major stages results in a slowdown on our benchmark CPU), so the reference is single-threaded. The Halide algorithm is 34 lines, and compiles to an implementation 4. 2× faster than the original. The speedup comes from a combination of parallelism, tile-level fusion of some stages, and careful reordering of dimensions to control parallel grain size in the grid. We also compared our implementation to a hand-tuned GPU implementation from the original authors, written in 370 lines of CUDA code.
The same Halide algorithm-less than 1/10th the code-found a different schedule which was 2. 3× faster than the hand-written CUDA. The Halide compiler generates similar CUDA code to the reference, but the autotuner found an unintuitive point in the schedule space which sacrificed some parallelism in the grid construction step to reduce synchronization overhead in the scattering reduction. It also uses a tiled fusion strategy which passes intermediate results through GPU scratchpad memory to improve locality through the blur steps at the expense of redundant computation. These tradeoffs were counter-intuitive to the original author, and also much harder to express in CUDA, but are easily described by our schedule representation and found by our autotuner. Local Laplacian filters uses a multi-scale approach to tone map images and enhance local contrast in an edge-respecting fashion  [3, 22].
The Halide version was written in one day, in 52 lines of code. It compiles to an implementation which is 1. 7× faster than the highly optimized expert implementation (roughly 20× faster than the clean C++ without IPP and OpenMP). The resulting schedule is enormously complex, mixing different fusion, tiling, vectorization, and multithreading strategies throughout the expansive 99 stage graph. In C, it would correspond to hundreds of loops over more than 10,000 lines of code. The same program compiles with a different automatically generated schedule to a hybrid CPU/GPU program with 58 unique GPU kernels, each representing a differently tiled and partially fused subset of the overall graph, and with the lookup table and several smaller levels of the pyramids scheduled as vector code on the CPU.
The generated program has more distinct CUDA kernels than the Halide algorithm describing it has lines of code. It runs 7. 5× faster than the hand-tuned Adobe implementation, and is more than 4× faster than the best parallel vector implementation on the CPU. This This is compared to the result of running the autotuner directly on the target resolution. We report the ratio of the cross-tested time to the autotuned-on-target time as the "slowdown. " Note that schedules generalize better from low resolutions to high resolutions. In theory the slow-down should always be at least one, but due to the stochastic nature of the search some schedules were slower when autotuned on the target. is by far the fastest implementation of local Laplacian filters we know of.
Past compilers have automatically synthesized parallel loop nests with overlapped tiling on CPUs and GPUs using the polyhedral model  [13, 16]. These compilers focussed on synthesizing high quality code given a single, user-defined set of overlapped tiling parameters. Autotuning has also been applied to iterated stencil computations, but past tuning work has focussed on exhaustive search of small parameter spaces for one or a few strategies  [15]. Image Processing Languages Critically, many optimizations for iterated stencil computations are based on the assumption that the time dimension of iteration is large relative to the spatial dimension of the grid. In image processing pipelines, most individual stencils are applied only once, while images are millions of pixels in size. Image processing pipelines also include more types of computation than stencils alone, and scheduling them requires choices not only of different parameters, but of entirely different strategies, for each of many heterogeneous stages, which is infeasible with either exhaustive search or polyhedral optimization.
Most prior image processing languages and systems have focused on efficient expression of individual kernels, as well as simple fusion in the absence of stencils  [6, 8, 23, 27]. Recently, Cornwall et al. demonstrated fast GPU code generation for image processing code using polyhedral optimization  [7]. Earlier work on the Halide language included a weaker model of schedules, and required programmers to explicitly specify schedules by hand  [26]. This is the first automatic optimizer, and therefore the first fully automatic compiler, for Halide programs. We show how they can be automatically inferred, starting from just the algorithm defining the pipeline stages, and using relatively little domain-specific knowledge beyond the ability to enumerate points in the space of schedules. Our state-of-the-art performance shows the effectiveness of our scheduling model for representing the underlying choice space.
Next, sliding window optimization and storage folding remove redundant computation and excess storage where the storage granularity is above the compute granularity. A simple flattening transform converts multidimensional coordinates in the infinite domain of each function into simple one-dimensional indices relative to the base of the corresponding buffer. Vectorization and unrolling passes replace loops of constant with k scheduled as vectorized or unrolled with the corresponding k-wide vector code or k copies of the loop body. Finally, backend code generation emits machine code for the scheduled pipeline via LLVM.
Acknowledgments Eric Chan provided feedback and inspiration throughout the design of Halide, and helped compare our local Laplacian filters implementation to his in  Camera Raw. Jason Ansel  helped inform the design of our autotuner. This work was supported by  DOE  Award  DE-SC0005288 ,  NSF  grant  0964004 , grants from  Intel  and  Quanta , and gifts from  Cognex and Adobe.
Genome sequencing and assembly Leishmania (L. ) amazonensis DNA sequences were obtained using the whole-genome shotgun strategy  27  on a combination of 454 GS-FLX Titanium (Roche) and Solexa (Illumina, Inc. ) instruments from the University of North Carolina (UNC, USA) sequencing facility. The GS-FLX sequencer generated single-end fragment reads (454 reads) with a mean length of 315 bp. The Illumina Genome Analyzer generated 76-bp paired-end fragment reads (Solexa reads) with an average insert size of 400 bp. Using an Perl script developed in-house, Illumina reads were filtered out if the average Phred quality score was lower than 20. For 454 sequences, reads comprising fewer than 100 bp or more than 500 bp (5% of each side of the normal distribution of read sizes) and reads with more than 1 unknown nucleotide (N) also were filtered out.
The Solexa reads were assembled into longer scaffolds using the Velvet 0. 7. 56 de novo assembler  28  with a k-mer parameter of 43. This value was calculated using the Velvet Optimizer script (Victorian Bioinformatics Consortium, Monash University, Australia), No Overlap detection and consensus generation were performed using the Minimus package. 30 The hybrid contigs were ordered and oriented with the Bambus program  31  using paired-end information and manual verification, which yielded 2627 scaffolds.
Combined gene models The above resources were used to automatically create L. (L. ) amazonensis gene models using EVidenceModeler (EVM, v. r03062010) software. 35 For individual outputs generated by Exonerate, Glimmer and Genemark. hmm were given values reflecting our data confidence to define gene structure. We considered the following confidence values: Glimmer ¼ 3, Genemark ¼ 3, ) amazonensis genome were assembled into 2627 scaffolds and 8100 genes were predicted using comparative and ab initio prediction tools. The functional analysis of these predicted genes included: (i) AutoFACT functional annotation, which revealed that 45% of the predicted genes were unclassified or with unassigned function; (ii) screening for orthologous families of genes among Leishmania spp. (OrthoMCL); and (iii) screening for information about conserved protein domains deposited in CDD and PFAM databases.
570 The Genome Sequence of L. (L. ) amazonensis [Vol. 20, nucleotide-to-protein match ¼ 6. The gene model was considered reliable only if it was predicted by all ab initio software or if it had similarity with one of the compared species. A final set of predicted gene models was then selected and manually inspected. Incomplete genes or genes overlapping gap regions were inspected with input from blastx alignments against protein databases and scaffold edges.