5 Replies Latest reply on Feb 26, 2009 10:26 PM by riza.guntur

    How to split stream and recursion

    riza.guntur

      I am very curious in splitting stream into two, because I need it to implement merge sort using multiple stream processor for my paper. Anyone know?

      There is one thing that really make me confuse, that is in binary search in brook+ tutorial, because I don't see any recursion there.

      Any help I will greatly appreciate.

        • How to split stream and recursion
          rick.weber

          Recursion is not possible in Brook+, because all functions are inlined. As for splitting streams, this is going to require multiple kernel calls, which may significantly impact your performance. You might be able to implement merge sort in CAL, as it does allow recursion, but using the global array is going to be tricky; especially if you're sorting an array with lots of elements.

            • How to split stream and recursion
              rahulgarg

              Even with CAL, the function call stack depth is limited (to 16 i think).

              So you are better off not doing recursion.

               

              • How to split stream and recursion
                riza.guntur

                 

                Originally posted by: rick.weber Recursion is not possible in Brook+, because all functions are inlined. As for splitting streams, this is going to require multiple kernel calls, which may significantly impact your performance. You might be able to implement merge sort in CAL, as it does allow recursion, but using the global array is going to be tricky; especially if you're sorting an array with lots of elements.

                 

                So how do I can split stream if I can't access the index? Or do I can?

                I really confuse. One thing I understand very well is just sum.br

                O yeah, why all indexof examples in samples all involving 2 dimensional data or higher, how could I know for one dimensional. OMG this Brook+ really really hard.

                  • How to split stream and recursion
                    rick.weber

                    Brook+ does take some getting used to. Just realize that you can only write to the current point in the domain of execution. As for splitting a stream, you can basically do this by passing an index stream and selecting the inputs you want to be in your output.

                    so, if x = {1, 2, 3, 4, 5, 6}

                    index = {3, 5}

                    result is 2x1

                    and the kernel is:

                    kernel void split(float x[], float index<>, out float result<>
                    {
                    result = x[index];
                    }

                    result = {4, 6} after this kernel is run

                    This is how they do a sparse matrix multiply located in the samples directory.