How to simply synchronize?

[zealbell]

int size = 10;
int sum = 0; 
for (@Parallel int i = 0; i < size; i++) {
       sum +=  i * 2;//race condition 
}

For non expert GPU developers employing loop parallelization via annotations is there a simple way to synchronize e.g. like lock an object the default way it is done in java

int size = 10;
int sum = 0; 
for (@Parallel int i = 0; i < size; i++) {
       synchronized (sum){//illegal synchronization 
             sum +=  i * 2;//prevented race condition 
       }
}

or simply employ atomic fields

[jjfumero]

We have two ways to express parallel kernels in TornadoVM:

1. With annotations (suitable for non-GPU experts and quick prototyping)
   a. @Parallel annotates Java loops that can be parallelizable.
   b. @Reduce annotates Java parameters used for reductions

   This option is easy to program because developers are not forced to think in parallel, but it is very limited. It works well for a lot of cases though, especially for the map-style computation.

2. Suitable for GPU experts (usually with CUDA/OpenCL expertise)
   The parallelism is explicit and it offers more low-level features. such as barriers, local/shared memory accesses, synchronization primitives, etc.

You can use any of those in your program.

Using Option 1

For your use case, if we use option 1:

void reduction(float[] input, @Reduce float[] output) {
   for (@Parallel int i = 0; i < input.length(); i++) {
       output[0]  +=  i * 2;
    }
}

TornadoVM will generate a few kernels under the hoods. Reductions in OpenCL/CUDA. etc are not that trivial.

Using Option 2

With this option, you are programming the parallel reduction directly from Java. Note that this code is not semantically correct if you run it in pure Java. You need the TornadoVM runtime to run this expression:

// Example of a reduction using GPU's local memory (OpenCL) / shared memory (CUDA) 

public static void reductionLocal(float[] a, float[] b, int localSize, KernelContext context) {
        int globalIdx = context.globalIdx;
        int localIdx = context.localIdx;
        int localGroupSize = context.localGroupSizeX;
        int groupID = context.groupIdx; // Expose Group ID

        float[] localA = context.allocateFloatLocalArray(256);
        localA[localIdx] = a[globalIdx];
 
       // Reduction
        for (int stride = (localGroupSize / 2); stride > 0; stride /= 2) {
            context.localBarrier();          // Barrier
            if (localIdx < stride) {
                localA[localIdx] *= localA[localIdx + stride] * 2;
            }
        }
   
       // Store the result in the first position of the work-group
        if (localIdx == 0) {
            b[groupID] = localA[0];
        }
    }

    
     // How to invoke this code:

        WorkerGrid worker = new WorkerGrid1D(size);
        GridScheduler gridScheduler = new GridScheduler();
        gridScheduler.setWorkerGrid("s0.t0", worker);
        KernelContext context = new KernelContext();

        TaskGraph taskGraph = new TaskGraph("s0") //
                .transferToDevice(DataTransferMode.EVERY_EXECUTION, input, localSize)//
                .task("t0", ReductionsLocalMemory::reductionLocal, input, reduce, localSize, context) //
                .transferToHost(DataTransferMode.EVERY_EXECUTION, reduce);

        // Change the Grid
        worker.setLocalWork(localSize, 1, 1);

        ImmutableTaskGraph immutableTaskGraph = taskGraph.snapshot();
        TornadoExecutionPlan executor = new TornadoExecutionPlan(immutableTaskGraph);
        executor.withGridScheduler(gridScheduler).execute();

        // The reduce variable will have partial reductions: We need another reduction for all values stored in the output array
       float sum = reduce[0];
       for (int i = 1; i < reduce.length(); i++) {
          sum += reduce[i] * 2;
      }

We have plenty of examples of the Kernel Context API and the Loop Parallel annotations in our test-suite:

• Kernel Context: https://github.com/beehive-lab/TornadoVM/tree/master/tornado-unittests/src/main/java/uk/ac/manchester/tornado/unittests/kernelcontext/reductions
• Reductions with @parallel: https://github.com/beehive-lab/TornadoVM/tree/master/tornado-unittests/src/main/java/uk/ac/manchester/tornado/unittests/reductions

[zealbell]

Thanks a lot for the detailed response. With the first option can the size of the annotated array (output) be > 1, I am at crossroads where the likely hood of doing something like

void reduction(float[] input, @Reduce float[] output) {
   for (@Parallel int i = 0; i < input.length(); i++) {
       output[0]  +=  i * 2;
       if(output[1]%5==0) output[1]  +=  i  * 0.5f;
    }
}

is inevitable

[jjfumero]

Multiple reductions within the same expression (kernel) are not supported with the Loop Parallel API. In these cases, you can use the Kernel Context API (needs OpenCL/CUDA knowledge though).

[zealbell]

Hi, I am having some issues with reduction

        public void reduce(float[] input, @Reduce float[] result) {
//            result[0] = 0.0f;
//            for (@Parallel int i = 0; i < input.length; i++) {
//                result[0] += input[0];
//            }
            
            result[0] = 0.0f;
            for (@Parallel int i = 0; i < input.length; i++) {
                float value = 1.5f;
                result[0] += value;
            }
        }

with the uncommented code, I get this error

        WARNING: Using incubator modules: jdk.incubator.foreign, jdk.incubator.vector
Exception in thread "main" uk.ac.manchester.tornado.api.exceptions.TornadoInternalError: unimplemented
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.exceptions.TornadoInternalError.unimplemented(TornadoInternalError.java:53)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.graal.compiler.TornadoSnippetReflectionProvider.forBoxed(TornadoSnippetReflectionProvider.java:40)
	at jdk.internal.vm.compiler/org.graalvm.compiler.replacements.SnippetTemplate.forBoxed(SnippetTemplate.java:1675)
	at jdk.internal.vm.compiler/org.graalvm.compiler.replacements.SnippetTemplate.bind(SnippetTemplate.java:1621)
	at jdk.internal.vm.compiler/org.graalvm.compiler.replacements.SnippetTemplate.instantiate(SnippetTemplate.java:2003)
	at jdk.internal.vm.compiler/org.graalvm.compiler.replacements.SnippetTemplate.instantiate(SnippetTemplate.java:1966)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.graal.snippets.PTXGPUReduceSnippets$Templates.lower(PTXGPUReduceSnippets.java:989)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.graal.PTXLoweringProvider.lowerReduceSnippets(PTXLoweringProvider.java:354)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.graal.PTXLoweringProvider.lowerStoreAtomicsReduction(PTXLoweringProvider.java:337)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.graal.PTXLoweringProvider.lower(PTXLoweringProvider.java:232)
	at jdk.internal.vm.compiler/org.graalvm.compiler.nodes.spi.Lowerable.lower(Lowerable.java:40)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.common.LoweringPhase.process(LoweringPhase.java:591)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.common.LoweringPhase$ProcessFrame.preprocess(LoweringPhase.java:522)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.common.LoweringPhase.processBlock(LoweringPhase.java:690)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.common.LoweringPhase.lower(LoweringPhase.java:266)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.common.LoweringPhase.run(LoweringPhase.java:249)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.common.LoweringPhase.run(LoweringPhase.java:106)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.BasePhase.apply(BasePhase.java:261)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.BasePhase.apply(BasePhase.java:170)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.PhaseSuite.run(PhaseSuite.java:246)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.BasePhase.apply(BasePhase.java:261)
	at jdk.internal.vm.compiler/org.graalvm.compiler.phases.BasePhase.apply(BasePhase.java:170)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.graal.compiler.PTXCompiler.emitFrontEnd(PTXCompiler.java:235)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.graal.compiler.PTXCompiler.compile(PTXCompiler.java:114)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.graal.compiler.PTXCompiler$PTXCompilationRequest.execute(PTXCompiler.java:519)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.graal.compiler.PTXCompiler.compileSketchForDevice(PTXCompiler.java:297)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.runtime.PTXTornadoDevice.compileTask(PTXTornadoDevice.java:176)
	at tornado.drivers.ptx@0.16-dev/uk.ac.manchester.tornado.drivers.ptx.runtime.PTXTornadoDevice.installCode(PTXTornadoDevice.java:145)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.TornadoVM.compileTaskFromBytecodeToBinary(TornadoVM.java:494)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.TornadoVM.execute(TornadoVM.java:757)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.TornadoVM.execute(TornadoVM.java:217)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.scheduleInner(TornadoTaskGraph.java:800)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.schedule(TornadoTaskGraph.java:1203)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TaskGraph.execute(TaskGraph.java:782)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.ImmutableTaskGraph.execute(ImmutableTaskGraph.java:73)
	at java.base/java.util.ArrayList.forEach(ArrayList.java:1511)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TornadoExecutionPlan$TornadoExecutor.execute(TornadoExecutionPlan.java:297)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TornadoExecutionPlan.execute(TornadoExecutionPlan.java:126)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.ReduceTaskGraph.executeExpression(ReduceTaskGraph.java:647)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.ReduceTaskGraph.scheduleWithReduction(ReduceTaskGraph.java:606)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.rewriteTaskForReduceSkeleton(TornadoTaskGraph.java:1079)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.reduceAnalysis(TornadoTaskGraph.java:1089)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.analyzeSkeletonAndRun(TornadoTaskGraph.java:1099)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.schedule(TornadoTaskGraph.java:1184)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TaskGraph.execute(TaskGraph.java:782)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.ImmutableTaskGraph.execute(ImmutableTaskGraph.java:73)
	at java.base/java.util.ArrayList.forEach(ArrayList.java:1511)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TornadoExecutionPlan$TornadoExecutor.execute(TornadoExecutionPlan.java:297)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TornadoExecutionPlan.execute(TornadoExecutionPlan.java:126)
	at Sandbox.InstanceReduction.main(InstanceReduction.java:81)

Then this error if I have other parameters with the reduction method alongside the @reduce float[]

	Reduce Operation no supported yet: snippet not installed
[Bailout] Running the sequential implementation. Enable --debug to see the reason.
Exception in thread "main" uk.ac.manchester.tornado.api.exceptions.TornadoRuntimeException: [ERROR] TornadoVM Bytecode not recognized
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.TornadoVM.throwError(TornadoVM.java:667)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.TornadoVM.execute(TornadoVM.java:782)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.TornadoVM.execute(TornadoVM.java:217)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.scheduleInner(TornadoTaskGraph.java:800)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.schedule(TornadoTaskGraph.java:1203)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TaskGraph.execute(TaskGraph.java:782)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.ImmutableTaskGraph.execute(ImmutableTaskGraph.java:73)
	at java.base/java.util.ArrayList.forEach(ArrayList.java:1511)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TornadoExecutionPlan$TornadoExecutor.execute(TornadoExecutionPlan.java:297)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TornadoExecutionPlan.execute(TornadoExecutionPlan.java:126)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.ReduceTaskGraph.executeExpression(ReduceTaskGraph.java:647)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.runReduceTaskGraph(TornadoTaskGraph.java:1074)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.analyzeSkeletonAndRun(TornadoTaskGraph.java:1101)
	at tornado.runtime@0.16-dev/uk.ac.manchester.tornado.runtime.tasks.TornadoTaskGraph.schedule(TornadoTaskGraph.java:1184)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TaskGraph.execute(TaskGraph.java:782)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.ImmutableTaskGraph.execute(ImmutableTaskGraph.java:73)
	at java.base/java.util.ArrayList.forEach(ArrayList.java:1511)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TornadoExecutionPlan$TornadoExecutor.execute(TornadoExecutionPlan.java:297)
	at tornado.api@0.16-dev/uk.ac.manchester.tornado.api.TornadoExecutionPlan.execute(TornadoExecutionPlan.java:126)

Also I would like to ask about support for multidimensional arrays. I have a method with a long[][] parameter as one of the inputs. Compilation isn't the issue this time. But I get this as parta my output

[TornadoVM-PTX-JNI] ERROR : cuMemcpyHtoDAsync -> Returned: 1

[jjfumero]

Hi @54LiNKeR ,
it seems there are some problems in TornadoVM for simple reductions. For the simple case you shared, it should work. We will annotate the issue and provide a patch.

Regarding multi-dimensional arrays, that's currently a limitation, not only for reductions for also for other types of computation:
https://tornadovm.readthedocs.io/en/latest/programming.html#parallel-reductions

To overcome this limitation, the TornadoVM API offers Java types for 1D-3D data structures, such as arrays.
https://github.com/beehive-lab/TornadoVM/tree/master/tornado-api/src/main/java/uk/ac/manchester/tornado/api/collections/types

We are actually working to provide more of these types that can be processed more efficiently within TornadoVM.