001/*
002 * To change this template, choose Tools | Templates
003 * and open the template in the editor.
004 */
005
006package com.nativelibs4java.opencl.util;
007
008import com.nativelibs4java.opencl.*;
009import java.io.FileNotFoundException;
010import java.io.IOException;
011import java.io.InputStream;
012import java.nio.Buffer;
013import java.util.LinkedHashMap;
014import java.util.Map;
015import java.util.logging.Level;
016import java.util.logging.Logger;
017
018import com.nativelibs4java.util.IOUtils;
019import com.nativelibs4java.util.Pair;
020
021import org.bridj.Pointer;
022import org.bridj.Platform;
023import static org.bridj.Pointer.*;
024
025/**
026 * Parallel reduction utils (max, min, sum and product computations on OpenCL buffers of any type)
027 * @author Olivier
028 */
029public class ReductionUtils {
030        static final int DEFAULT_MAX_REDUCTION_SIZE = 4;
031        
032    static String source;
033    static final String sourcePath = ReductionUtils.class.getPackage().getName().replace('.', '/') + "/" + "Reduction.c";
034    static synchronized String getSource() throws IOException {
035        InputStream in = Platform.getClassLoader(ReductionUtils.class).getResourceAsStream(sourcePath);
036        if (in == null)
037            throw new FileNotFoundException(sourcePath);
038        return source = IOUtils.readText(in);
039    }
040
041    public enum Operation {
042        Add,
043        Multiply,
044        Min,
045        Max;
046    }
047    
048    public static Pair<String, Map<String, Object>> getReductionCodeAndMacros(Operation op, OpenCLType valueType, int channels) throws IOException {
049        Map<String, Object> macros = new LinkedHashMap<String, Object>();
050        String cType = valueType.toCType() + (channels == 1 ? "" : channels);
051        macros.put("OPERAND_TYPE", cType);
052        String operation, seed;
053        switch (op) {
054            case Add:
055                operation = "_add_";
056                seed = "0";
057                break;
058            case Multiply:
059                operation = "_mul_";
060                seed = "1";
061                break;
062            case Min:
063                operation = "_min_";
064                switch (valueType) {
065                    case Int:
066                        seed = Integer.MAX_VALUE + "";
067                        break;
068                    case Long:
069                        seed = Long.MAX_VALUE + "LL";
070                        break;
071                    case Short:
072                        seed = Short.MAX_VALUE + "";
073                        break;
074                    case Float:
075                        seed = "MAXFLOAT";
076                        break;
077                    case Double:
078                        seed = "MAXDOUBLE";
079                        break;
080                    default:
081                        throw new IllegalArgumentException("Unhandled seed type: " + valueType);
082                }
083                
084                break;
085            case Max:
086                operation = "_max_";
087                switch (valueType) {
088                    case Int:
089                        seed = Integer.MIN_VALUE + "";
090                        break;
091                    case Long:
092                        seed = Long.MIN_VALUE + "LL";
093                        break;
094                    case Short:
095                        seed = Short.MIN_VALUE + "";
096                        break;
097                    case Float:
098                        seed = "-MAXFLOAT";
099                        break;
100                    case Double:
101                        seed = "-MAXDOUBLE";
102                        break;
103                    default:
104                        throw new IllegalArgumentException("Unhandled seed type: " + valueType);
105                }
106                break;
107            default:
108                throw new IllegalArgumentException("Unhandled operation: " + op);
109        }
110        macros.put("OPERATION", operation);
111        macros.put("SEED", seed);
112        return new Pair<String, Map<String, Object>>(getSource(), macros);
113    }
114    public interface Reductor<B> {
115        /** Number of independent channels of the reductor */
116        public int getChannels();
117        public CLEvent reduce(CLQueue queue, CLBuffer<B> input, long inputLength, CLBuffer<B> output, int maxReductionSize, CLEvent... eventsToWaitFor);
118        public Pointer<B> reduce(CLQueue queue, CLBuffer<B> input, long inputLength, int maxReductionSize, CLEvent... eventsToWaitFor);
119        public CLEvent reduce(CLQueue queue, CLBuffer<B> input, long inputLength, Pointer<B> output, int maxReductionSize, CLEvent... eventsToWaitFor);
120        /** 
121         * Return the result of the reduction operation (with one value per channel).
122         */
123        public Pointer<B> reduce(CLQueue queue, CLBuffer<B> input, CLEvent... eventsToWaitFor);
124        
125    }
126    /*public interface WeightedReductor<B extends Buffer, W extends Buffer> {
127        public CLEvent reduce(CLQueue queue, CLBuffer<B> input, CLBuffer<W> weights, long inputLength, B output, int maxReductionSize, CLEvent... eventsToWaitFor);
128        public CLEvent reduce(CLQueue queue, CLBuffer<B> input, CLBuffer<W> weights, long inputLength, CLBuffer<B> output, int maxReductionSize, CLEvent... eventsToWaitFor);
129    }*/
130    static int getNextPowerOfTwo(int i) {
131        int shifted = 0;
132        boolean lost = false;
133        for (;;) {
134            int next = i >> 1;
135            if (next == 0) {
136                if (lost)
137                    return 1 << (shifted + 1);
138                else
139                    return 1 << shifted;
140            }
141            lost = lost || (next << 1 != i);
142            shifted++;
143            i = next;
144        }
145    }
146
147    /**
148     * Create a reductor for the provided operation and primitive type (on the provided number of independent channels).<br>
149     * Channels are reduced independently, so that with 2 channels the max of elements { (1, 30), (2, 20), (3, 10) } would be (3, 30).
150     */
151    public static <B> Reductor<B> createReductor(final CLContext context, Operation op, final OpenCLType valueType, final int valueChannels) throws CLBuildException {
152        try {
153
154
155            Pair<String, Map<String, Object>> codeAndMacros = getReductionCodeAndMacros(op, valueType, valueChannels);
156            CLProgram program = context.createProgram(codeAndMacros.getFirst());
157            program.defineMacros(codeAndMacros.getValue());
158            program.build();
159            CLKernel[] kernels = program.createKernels();
160            if (kernels.length != 1)
161                throw new RuntimeException("Expected 1 kernel, found : " + kernels.length);
162            final CLKernel kernel = kernels[0];
163            return new Reductor<B>() {
164                @Override
165                public int getChannels() {
166                                return valueChannels;
167                }
168                                @SuppressWarnings("unchecked")
169                public CLEvent reduce(CLQueue queue, CLBuffer<B> input, long inputLength, Pointer<B> output, int maxReductionSize, CLEvent... eventsToWaitFor) {
170                    Pair<CLBuffer<B>, CLEvent[]> outAndEvts = reduceHelper(queue, input, (int)inputLength, maxReductionSize, eventsToWaitFor);
171                    return outAndEvts.getFirst().read(queue, 0, valueChannels, output, false, outAndEvts.getSecond());
172                }
173                @Override
174                public Pointer<B> reduce(CLQueue queue, CLBuffer<B> input, long inputLength, int maxReductionSize, CLEvent... eventsToWaitFor) {
175                    Pointer<B> output = Pointer.allocateArray((Class)valueType.type, valueChannels).order(context.getByteOrder());
176                    CLEvent evt = reduce(queue, input, inputLength, output, maxReductionSize, eventsToWaitFor);
177                    //queue.finish();
178                    //TODO
179                    evt.waitFor();
180                    return output;
181                }
182                @Override
183                public Pointer<B> reduce(CLQueue queue, CLBuffer<B> input, CLEvent... eventsToWaitFor) {
184                                return reduce(queue, input, input.getElementCount(), DEFAULT_MAX_REDUCTION_SIZE, eventsToWaitFor);
185                }
186                @Override
187                public CLEvent reduce(CLQueue queue, CLBuffer<B> input, long inputLength, CLBuffer<B> output, int maxReductionSize, CLEvent... eventsToWaitFor) {
188                    Pair<CLBuffer<B>, CLEvent[]> outAndEvts = reduceHelper(queue, input, (int)inputLength, maxReductionSize, eventsToWaitFor);
189                    return outAndEvts.getFirst().copyTo(queue, 0, valueChannels, output, 0, outAndEvts.getSecond());
190                }
191                @SuppressWarnings("unchecked")
192                                public Pair<CLBuffer<B>, CLEvent[]> reduceHelper(CLQueue queue, CLBuffer<B> input, int inputLength, int maxReductionSize, CLEvent... eventsToWaitFor) {
193                                        if (inputLength == 1) {
194                                                return new Pair<CLBuffer<B>, CLEvent[]>(input, new CLEvent[0]);
195                                        }
196                    if (inputLength == 1) {
197                                                return new Pair<CLBuffer<B>, CLEvent[]>(input, new CLEvent[0]);
198                                        }
199                    CLBuffer<?>[] tempBuffers = new CLBuffer<?>[2];
200                    int depth = 0;
201                                        CLBuffer<B> currentOutput = null;
202                                        CLEvent[] eventsArr = new CLEvent[1];
203                                        int[] blockCountArr = new int[1];
204
205                    int maxWIS = (int)queue.getDevice().getMaxWorkItemSizes()[0];
206
207                    while (inputLength > 1) {
208                        int blocksInCurrentDepth = inputLength / maxReductionSize;
209                                                if (inputLength > blocksInCurrentDepth * maxReductionSize)
210                                                        blocksInCurrentDepth++;
211                        
212                                                int iOutput = depth & 1;
213                        CLBuffer<?> currentInput = depth == 0 ? input : tempBuffers[iOutput ^ 1];
214                        currentOutput = (CLBuffer<B>)tempBuffers[iOutput];
215                        if (currentOutput == null)
216                            currentOutput = (CLBuffer<B>)(tempBuffers[iOutput] = context.createBuffer(CLMem.Usage.InputOutput, valueType.type, blocksInCurrentDepth * valueChannels));
217                                                
218                        synchronized (kernel) {
219                            kernel.setArgs(currentInput, (long)blocksInCurrentDepth, (long)inputLength, (long)maxReductionSize, currentOutput);
220                            int workgroupSize = blocksInCurrentDepth;
221                            if (workgroupSize == 1)
222                                        workgroupSize = 2;
223                            blockCountArr[0] = workgroupSize;
224                            eventsArr[0] = kernel.enqueueNDRange(queue, blockCountArr, null, eventsToWaitFor);
225                        }
226                                                eventsToWaitFor = eventsArr;
227                                                inputLength = blocksInCurrentDepth;
228                        depth++;
229                    }
230                    return new Pair<CLBuffer<B>, CLEvent[]>(currentOutput, eventsToWaitFor);
231                }
232
233            };
234        } catch (IOException ex) {
235            Logger.getLogger(ReductionUtils.class.getName()).log(Level.SEVERE, null, ex);
236            throw new RuntimeException("Failed to create a " + op + " reductor for type " + valueType + valueChannels, ex);
237        }
238    }
239}