Parallel Computing Framework

Introduction

GTB contains chromosome hierarchy information as well as natural chunking of the GTB, and parallel computation based on the GTB format is very easy to perform with multiple optional ways:

• Chromosome-level: Each sub-thread processes one of the chromosome, and joins the data by chromosome after completing the task. This is suitable for case where upstream and downstream variants of the same chromosome need to be scanned (e.g. LD calculations). Since each chromosome contains a different amount of variants, this parallelism can lead to unequal tasking of threads and parallelism does not work when the GTB contains only a single chromosome.
• Block-level: Performs parallel computation in GTB chunks, with each (or a small number of) chunks assigned to a sub-thread for processing, and outputs to file or saves the data using CLM algorithms when finished. This is suitable for situations where the computational task is focused on a single locus and requires ordered, large output to a file that does not use additional disk space (e.g., variant locus queries or sample screening). Since the CLM output algorithm requires the use of memory to temporarily store data, this parallel approach requires tight control over the amount of memory.
• Variant-level: The entire GTB file is divided equally by the number of bits into multiple subparts, each of which is processed by a subthread. Suitable for scenarios where the computation task is focused on a single bit, this parallelism can satisfy most application requirements.

The above parallelism can be combined with each other, for example, by performing tasks at the chromosome-level, and then using variant-level parallelism for each chromosome.

Block-level parallel computing is often used for file format conversion of GTB, e.g., GTB format to VCF format and GTB format to TSV format, which are not described here because of the more complex memory control and output control involved.

Parallel Computation at the Chromosome-level

Chromosome-level parallel computation is performed by assigning the chromosome objects to be processed by the main thread, and each sub-thread processes the corresponding chromosomes in turn. The following is an example program for parallel computation of coordinate-ordered GTB at the chromosome level:

int nThreads = 6;

// load GTB
GTBManager manager = GTBManager.load("<path_to_GTB>");

// create a thread pool
ThreadPool threadPool = new ThreadPool(nThreads);

// open GTBReader
BaseArray<Chromosome> chromosomes = new Array<>(manager.getIndexer().getChromosomes());

threadPool.submit(() -> {
    // get the GTBReader for current working thread
    GTBReader reader = manager.instanceReader();
    Chromosome chromosome;
    while (true) {
        // get the task chromosome for current working thread
        synchronized (chromosomes) {
            if (chromosomes.size() > 0) {
                chromosome = chromosomes.popFirst();
            } else {
                break;
            }
        }

        // limit the GTBReader to read the variants with the specified chromosome
        reader.limit(manager.getIndexer().getVariantIndexRange(chromosome));
        reader.seek(0);

        Variant variant;
        while ((variant = reader.read()) != null) {
            // get genotype array of variant
            Genotypes genotypes = (Genotypes) variant.getProperty(IGenotypes.class);

            // TODO
        }
    }

    reader.close();
    return true;
}, nThreads);
threadPool.close();

When GTB is coordinate-ordered, the GTBIndexer precisely identifies the pointer range of variants for each chromosome, and this parallel approach does not incur additional IO overhead. An example of a computational program using this framework is LDCalculator.

Exceptions will be thrown by manager.getIndexer().getChromosomes() when the GTB is out of order by coordinates. One solution strategy is to use GTBSorter to sort and then perform the computation process. Another solution strategy is to use GTBFilter:

int nThreads = 6;

// load GTB
GTBManager manager = GTBManager.load("<path_to_GTB>");

// create a thread pool
ThreadPool threadPool = new ThreadPool(getThreads());

// open GTBReader
BaseArray<Chromosome> chromosomes = new Array<>(Chromosome.identifiableList());

threadPool.submit(() -> {
    // instantiate the GTBReader for current working thread
    GTBReader reader = manager.instanceReader();
    Chromosome chromosome;
    GTBFilter filter = new GTBFilter();
    while (true) {
        synchronized (chromosomes) {
            if (chromosomes.size() > 0) {
                chromosome = chromosomes.popFirst();
            } else {
                break;
            }
        }

        // limit the GTBReader to read the variants with the specified chromosome
        filter.clear();
        filter.filterByChromosome(chromosome);
        reader.seek(0);
        Variant variant;
        while ((variant = reader.read(filter)) != null) {
            // get genotype array of variant
            Genotypes genotypes = (Genotypes) variant.getProperty(IGenotypes.class);

            // TODO
        }
    }

    reader.close();
    return true;
}, nThreads);
threadPool.close();

In this case, even if the GTB contains only one chromosome, it will cause the coordinate field to be scanned multiple times and is only suitable for use when writing general purpose calculation programs.

Parallel Computation at the Variant-level

Parallel computation at the variant-level is performed by means of the GTBReader's part(int nThreads), which divides the GTBReader's readable pointer range equally into subparts, each of which is processed independently by a subthread. The following is an example program:

int nThreads = 6;

// load GTB
GTBManager manager = GTBManager.load("<path_to_GTB>");

// create a thread pool
ThreadPool threadPool = new ThreadPool(nThreads);

// open GTBReader
BaseArray<GTBReader> readers = manager.instanceReader().part(nThreads);

AtomicInteger threadId = new AtomicInteger(0);
threadPool.submit(() -> {
    // get the thread id and GTBReader for current working thread
    int localThreadId = threadId.getAndIncrement();
    GTBReader reader = readers.get(localThreadId);

    // read variants by row
    Variant variant;
    while ((variant = reader.read()) != null) {
        // get genotype array of variant
        Genotypes genotypes = (Genotypes) variant.getProperty(IGenotypes.class);

        // TODO
    }

    reader.close();
    return true;
}, readers.size());
threadPool.close();

An example of a computational program that uses this framework is edu.sysu.pmglab.gbc.GTBExporter.