In recent years, parallel architectures have become ubiquitous due to advancements in AI and cloud computing.However, parallel processing is not limited to x86 CISC CPUs and advanced graphics cards, GPUs; it also includes computations on ARM-based and RISC-V devices.In recent years, ARM processors have been adapted to incorporate an increasing number of cores.Today, mobile devices feature at least eight execution units, typically divided into energy-efficient and performance-oriented groups.RISC-based parallel processors are also integrated on development boards supported by the Linux kernel.In this article, we tested our NPDP Benchmark Suite for non-serial polyadic dynamic programming, primarily in the field of computer algorithms and bioinformatics, to evaluate the performance of the RISC processors under study, as well as code locality and cache efficiency.The benchmark consists of 10 kernels written in C++ and OpenMP.In the Android environment, we used the JAVA NDK (Native Development Kit) to port the application.For Apple machines, we used a port to OpenMP for parallelization.For the RISC-V native Linux environment, we applied the native Linux setup for efficient execution.Finally, we summarized the article and outlined future work.

RNA folding can be compared to the process of knowledge extraction, as it involves extracting hidden information from the RNA nucleotide sequence to predict its 3D structure. Just like in knowledge extraction from large datasets, RNA folding uses various algorithms and mathematical models to analyze input data (RNA sequence) and uncover how the RNA molecule adopts its final form. Thus, RNA folding aims to understand how genetic information encoded in the nucleotide sequence translates into a functional molecular structure. RNA folding algorithms focus on constructing a large matrix using dynamic programming, which accounts for the majority of the computations. The Nussinov-like algorithms for RNA folding are fundamental non-serial polyadic dynamic programming codes (NPDP) for testing non-uniform dependency analysis, multi-core CPUs and GPUs, loop tiling transformations, and source-to-source techniques, as well as manual approaches. In this article, we first analyze the achievements in optimizing this code over the past two decades, discussing fully automated methods based on loop tiling and the polyhedral model, manual methods involving transposition, row- and square blocking, as well as the Four Russians technique, its variations, and hybrids that reduce the algorithm’s complexity. Second, we propose a novel method that extends the polyhedral model through dependency analysis, combines features of loop tiling and manual techniques, and can be applied to both GPUs and CPUs. Moreover, the adopted approach allows for optimizing other similar bioinformatics codes. Our research is based on multi-core processors and the OpenMP and OpenCL standards to demonstrate usability across multiple platforms. We will also discuss its simplicity and performance compared to other reference models. Finally, we conduct an experimental study on six multi-core machines, including both CPUs and GPUs, to demonstrate that the proposed approach outperforms related methods.

This article addresses the use of codes from polyhedral compilers with tiled and parallel code designed for CPU processors, automatically generated as source-to-source OpenMP for NVIDIA GPU graphics cards using CUDA. In previous publications, we demonstrated that it is possible to use large language models (LLM) to translate code, generate kernels, and correctly manage memory transfers between the host and the device without manual effort. Unfortunately, when the target architecture is not taken into account in detail, the performance of code designed for CPUs leaves much to be desired when running on GPUs. The architectural differences between these two platforms like cores, cache, and the dimensionality of computations require careful attention to performance portability . In this article, we address the Nussinov algorithm, a popular benchmark in bioinformatics, to achieve higher performance on the NVIDIA platform than automatically generated codes by LLM. Nussinov’s loop nests are a non-trivial kernel from the non-serial polyadic dynamic programming (NPDP) benchmark with non-uniform loops. We will utilize a polyhedral code framework that tiles and then manually modifies the most nested loop nest containing the majority of the computations, using the two-dimensional thread blocks. To accelerate the computations, shared memory within blocks is utilized. The resulting codes were tested on two modern NVIDIA devices for various RNA sequence lengths , compared to parallel and tiled CPU codes, and previously generated Nussinov’s GPU codes using LLMs. The correctness of these codes and their scalability were analyzed. Comparison to related approaches and future work are outlined.

In recent years, a multitude of AI solutions has emerged to facilitate code generation, commonly known as Language Model-based Programming (LLM).These tools empower programmers to automate their work.Automatic programming also falls within the domain of optimizing compilers, primarily based on the polyhedral model, which processes loop nests concentrating most computations.This article focuses on harnessing LLM tools to generate OpenCL code for non-serial polyadic dynamic programming kernels.[1] We have chosen the Nussinov RNA folding computational task, previously employed to test polyhedral compilers in optimizing kernels with non-uniform dependences.The code generated in OpenMP by polyhedral optimizers is limited to CPU computations.We automatically convert it into the OpenCL standard using ChatGPT-3.5 through its source-to-source queries to extend the number of possible platforms.The validity and efficiency of the generated code were verified on various CPUs and GPUs from different manufacturers.

In this paper, we present the application of three automatic source-to-source compilers to code implementing Mc-Caskill's bioinformatics algorithm.It computes probabilities of various substructures for RNA prediction.McCaskill's algorithm is compute and data intensive and it is within dynamic programming.A corresponding programming code exposes nonuniform dependences that complicate tiling of that code.The corresponding code is represented within the polyhedral model.Its optimization is still a challenging task for optimizing compilers employing multi-threaded loop tiling.To generate optimized code, we used the popular PLuTo compiler that finds and applies affine transformations, the TRACO compiler based on calculating the transitive closure of loop dependence graphs, and the newest polyhedral tool DAPT implementing space-time tiling.An experimental study fulfilled on two multi-core machines: an AMD Epyc with 64 threads and a 2x Intel Xeon Platinum 9242 with 192 threads demonstrates considerable speedup, high locality, and scalability for various problem sizes and the number of threads of generated codes by means of space-time tiling.

We present parallel tiled optimized McCaskill's partition functions computation code.That CPU and memory intensive dynamic programming task is within computational biology.To optimize code, we use the authorial source-to-source TRACO compiler and compare obtained code performance to that generated with the state-of-the-art PluTo compiler based on the affine transformations framework (ATF).Although PLuTo generates tiled code with outstanding locality, it fails to parallelize tiled code.A TRACO tiling strategy uses the transitive closure of a dependence graph to avoid affine function calculation.The ISL scheduler is used to parallelize tiled loop nests.An experimental study carried out on a multi-core computer demonstrates considerable speed-up of generated code for the larger number of threads.

BACKGROUND: An RNA primary structure, or sequence, is a single strand considered as a chain of nucleotides from the alphabet AUGC (adenine, uracil, guanine, cytosine). The strand can be folded onto itself, i.e., one segment of an RNA sequence might be paired with another segment of the same RNA sequence into a two-dimensional structure composed by a list of complementary base pairs, which are close together with the minimum energy. That list is called RNA's secondary structure and is predicted by an RNA folding algorithm. RNA secondary structure prediction is a computing-intensive task that lies at the core of search applications in bioinformatics. RESULTS: We suggest a space-time tiling approach and apply it to generate parallel cache effective tiled code for RNA folding using Nussinov's algorithm. CONCLUSIONS: Parallel tiled code generated with a suggested space-time loop tiling approach outperforms known related codes generated automatically by means of optimizing compilers and codes produced manually. The presented approach enables us to tile all the three loops of Nussinov's recurrence that is not possible with commonly known tiling techniques. Generated parallel tiled code is scalable regarding to the number of parallel threads - increasing the number of threads reduces code execution time. Defining speed up as the ratio of the time taken to run the original serial program on one thread to the time taken to run the tiled program on P threads, we achieve super-linear speed up (a value of speed up is greater than the number of threads used) for parallel tiled code against the original serial code up to 32 threads and super-linear speed up scalability (increasing speed up with increasing the thread number) up to 8 threads. For one thread used, speed up is about 4.2 achieved on an Intel Xeon machine used for carrying out experiments.

BACKGROUND: RNA folding is an ongoing compute-intensive task of bioinformatics. Parallelization and improving code locality for this kind of algorithms is one of the most relevant areas in computational biology. Fortunately, RNA secondary structure approaches, such as Nussinov's recurrence, involve mathematical operations over affine control loops whose iteration space can be represented by the polyhedral model. This allows us to apply powerful polyhedral compilation techniques based on the transitive closure of dependence graphs to generate parallel tiled code implementing Nussinov's RNA folding. Such techniques are within the iteration space slicing framework - the transitive dependences are applied to the statement instances of interest to produce valid tiles. The main problem at generating parallel tiled code is defining a proper tile size and tile dimension which impact parallelism degree and code locality. RESULTS: To choose the best tile size and tile dimension, we first construct parallel parametric tiled code (parameters are variables defining tile size). With this purpose, we first generate two nonparametric tiled codes with different fixed tile sizes but with the same code structure and then derive a general affine model, which describes all integer factors available in expressions of those codes. Using this model and known integer factors present in the mentioned expressions (they define the left-hand side of the model), we find unknown integers in this model for each integer factor available in the same fixed tiled code position and replace in this code expressions, including integer factors, with those including parameters. Then we use this parallel parametric tiled code to implement the well-known tile size selection (TSS) technique, which allows us to discover in a given search space the best tile size and tile dimension maximizing target code performance. CONCLUSIONS: For a given search space, the presented approach allows us to choose the best tile size and tile dimension in parallel tiled code implementing Nussinov's RNA folding. Experimental results, received on modern Intel multi-core processors, demonstrate that this code outperforms known closely related implementations when the length of RNA strands is bigger than 2500.

A challenging task in numerical programming modern computer systems is to effectively exploit the parallelism available in the architecture and manage the CPU caches to increase performance.Loop nest tiling allows for both coarsening parallel code and improving code locality.In this paper, we explore a new way to generate tiled code and derive the free schedule of tiles by means of the transitive closure of loop nest dependence graphs.Multi-threaded code executes tiles as soon as their operands are available.To design the approach, loop dependences are presented in the form of tuple relations.Discussed techniques are implemented in the source-to-source TRACO compiler.Experimental study, carried out on multi-core architectures, demonstrates the considerable speed-up of tiled numerical codes generated by the presented approach.

BACKGROUND: RNA secondary structure prediction is a compute intensive task that lies at the core of several search algorithms in bioinformatics. Fortunately, the RNA folding approaches, such as the Nussinov base pair maximization, involve mathematical operations over affine control loops whose iteration space can be represented by the polyhedral model. Polyhedral compilation techniques have proven to be a powerful tool for optimization of dense array codes. However, classical affine loop nest transformations used with these techniques do not optimize effectively codes of dynamic programming of RNA structure predictions. RESULTS: The purpose of this paper is to present a novel approach allowing for generation of a parallel tiled Nussinov RNA loop nest exposing significantly higher performance than that of known related code. This effect is achieved due to improving code locality and calculation parallelization. In order to improve code locality, we apply our previously published technique of automatic loop nest tiling to all the three loops of the Nussinov loop nest. This approach first forms original rectangular 3D tiles and then corrects them to establish their validity by means of applying the transitive closure of a dependence graph. To produce parallel code, we apply the loop skewing technique to a tiled Nussinov loop nest. CONCLUSIONS: The technique is implemented as a part of the publicly available polyhedral source-to-source TRACO compiler. Generated code was run on modern Intel multi-core processors and coprocessors. We present the speed-up factor of generated Nussinov RNA parallel code and demonstrate that it is considerably faster than related codes in which only the two outer loops of the Nussinov loop nest are tiled.

An iteration space visualizer is presented to analyze parallelism in loop nests including parallelism in tiled code of numerical programs.The tool visualizes exact data dependences available in arbitrarily nested loops as well as tiles generated with TRACO by means of the transitive closure of a loop nest dependence graph.Various graphical operations such as rotation, zooming, coloring and filtering allow for a detailed examination of dependences, iteration space slices, and shapes of generated tiles.The visualizer is a built-in TRACO module which collects results generated with TRACO and it is launched automatically when TRACO finishes code generation.The visualizer helps high-performance application developers discover parallelism available in loop nests and analyze tiled code produced by means of the polyhedral model.

We present the source-to-source TRACO compiler allowing for increasing program locality and parallelizing arbitrarily nested loop sequences in numerical applications.Algorithms for generation of tiled code and extracting synchronization-free slices composed of tiles are presented.Parallelism of arbitrary nested loops is obtained by creating a kernel of computations represented in the OpenMP standard to be executed independently on many CPUs.We consider benchmarks, typical from compute-intensive sequences of algebra operations or numerical computation from industry and engineering.The speed-up of programs generated by TRACO are discussed.Related compilers and techniques are considered.Future work is outlined.

Automatic coarse-grained parallelization of program loops is of great importance for multi-core computing systems. This paper presents a comparison of Iteration SpaceSlicing and Affine Transformation Framework algorithms aimed at extracting coarse-grained parallelism available in arbitrarily nested parameterized affine loops. We demonstrate that Iteration Space Slicing permits for extracting more coarse-grained parallelism in comparison to the Affine Transformation Framework. Experimental results show that by means of Iteration SpaceSlicing algorithms, we are able to extract coarse-grained parallelism for most loops of the NAS and UTDSP benchmarks, and that there is a strong need in devising advanced algorithms for calculating the exact transitive closure of dependence relations in order to increase the applicability of that framework.