Hi Chapel Team,
I was thinking about various approaches for implementing the project
to introduce barriers in 'forall' loop. I will have to perform a set
of transformations for this. Some example transformations are given
below.
* if (e1) { if (e2) S1; } ===> if (e1 && e2) S1;
* if (e) { S1; S2; } ===> v = e; if (v) S1; if (v) S2;
* forall ... { S1; S2 } ===> forall ... {S1}; forall {S2}
In addition I will have to introduce some data structures to do some
book keeping.
I feel I may take either of the following three approaches to
implement the transformations. Please share your comments and
suggestions on this. If you have any other methods please suggest.
1. Apply the transformations directly on the Chapel IR. Will this be a
difficult task to do?
2. Implement a source-to-source translator. Here we may take two approaches.
(i) Using the javacc and jtb framework [1]. Using this we can
generate a visitor pattern [2] based parser for Chapel . It requires
us to create a grammar for Chapel, which is not a tedious task. It
would take one week to do this. In worst case two weeks.
(ii) Using antlr [3]. It can also build a parse tree and we
can walk over it to build the translator. However, I could not find an
existing grammar for Chapel in antlr. I am not sure how challenging is
to build the grammar.
3. Apply transformations on the C code generated after Chapel
compilation. This does not sound natural, but it is a vague thought.
[1] http://web.cs.ucla.edu/~palsberg/course/cs239/S04/software.html
[2] http://www.cse.iitm.ac.in/~krishna/cs6013/lecture2.pdf
[3] http://www.antlr.org/
Regards,
On Thu, Mar 17, 2016 at 9:31 AM, raghesh <[email protected]> wrote:
> Thanks Vassily. I will address the points that you suggested in the proposal.
>
> On Thu, Mar 17, 2016 at 7:13 AM, Vassily Litvinov <[email protected]> wrote:
>> Hello Raghesh,
>>
>> Sorry for the delay on our end as well.
>>
>> Yes, such a barrier sounds like a useful feature. Do I understand it
>> correctly that the barrier is good to proceed if each iteration of the
>> forall loop has executed it once?
>
> Yes. You are right.
>
>>
>> If you'd like to make a project proposal for this feature, here are a couple
>> of suggestions for what would make your proposal stronger:
>>
>> * describe your ideas on how you will implement it
>>
>> * what iterators will it apply to? will it apply to ranges? domains? arrays?
>>
>> * what you see as potential extensions?
>>
>> * what application(s) would you write that exercise this feature?
>>
>> Be sure to let us know if you have further questions.
>>
>> Vassily
>>
>>
>> On 03/12/16 17:33, raghesh wrote:
>>>
>>> Hi Chapel Team,
>>>
>>> Sorry for the delay in sending this mail.
>>>
>>> I would like to give more clarity on the feature that I would like to
>>> add to the 'forall' loop.
>>>
>>> Please find the code below implemented in Chapel using the Barrier
>>> module available in Chapel. It was intended to use inside 'coforall',
>>> but I am using it inside 'forall' for the sake of explanation.
>>>
>>> use Barrier;
>>>
>>> here.maxTaskPar = 4;
>>> // here.maxTaskPar = 2;
>>> const numTasks = here.maxTaskPar;
>>> var b = new Barrier(numTasks);
>>>
>>> var A: [1..5] int, D: [1..4] int;
>>> var B = [1, 2, 3, 4];
>>>
>>> proc workload (i: int) {
>>> A[i] = B[i] - 1; // S1
>>> b.barrier();
>>> D[i] = A[i+1] * 2; // S2
>>> }
>>> forall i in 1..4 {
>>> workload(i);
>>> }
>>>
>>> writeln(D);
>>> delete b;
>>>
>>> Assume that the barrier (b.barrier()) inside 'workload' function is
>>> placed by the programmer so that all iterations of the 'forall' loop
>>> finish executing S1 and then S2 (we may denote it as S1 ; S2). So the
>>> expected values in arrays A and D are [0 1 2 3 0] and [2 4 6 0],
>>> respectively.
>>>
>>> Here since 'here.maxTaskPar' is set to 4 which is equal to the number
>>> of iterations of the 'forall' loop, we get expected results. But if we
>>> set 'here.maxTaskPar = 2', we get a different output. The code may
>>> even hang if there are 3 tasks. The user should get a consistent
>>> output irrespective of the number of tasks. From the users perspective
>>> it may be easy to think that there are as many tasks as number of
>>> iterations the 'forall' loop. But creating as many number of tasks as
>>> iterations may be very expensive.
>>>
>>> Here the objective is "the user should get the output as if there are
>>> as many number of tasks as number of iterations of the 'forall' loop.
>>> In case of Chapel we may call this kind of programming model as
>>> 'Unique Task model' unlike 'Unique Worker model' in OpenMP'.
>>>
>>> We may solve this issue in the above example by just inlining the
>>> 'workload' function call followed by a loop distribution of the
>>> 'forall' loop across the barrier.
>>>
>>> But the issue is more complicated when the barrier is deep inside
>>> 'if', while or 'procedures'. For instance the user may write the code
>>> as follows.
>>>
>>> forall i in 1..4 {
>>> if (i % 2 == 0) {
>>> S1;
>>> b.barrier(); // b1
>>> S2;
>>> }
>>> if (i % 2 == 1) {
>>> S3;
>>> b.barrier(); // b2
>>> S4;
>>> }
>>> }
>>>
>>> In 'Unique Task model' the user intends here to execute S1 and S3 in
>>> parallel in sequence with S2 and S4 executed in parallel (denoted as
>>> S1 || S3; S2 || S4). Even if the two barriers (b1 and b2) are placed
>>> textually apart in the code the user wants it to act as a global
>>> barrier which synchronizes among all the iterations of the 'forall'
>>> loop as if there are are as many number of tasks as iterations.
>>> Arguably this style of writing the code is useful since the programmer
>>> can first think about the statements to be put inside various
>>> conditions (S1 and S2 in 'if' statement and S3 and S4 in the second)
>>> and later he/she can think about placing barriers among these
>>> statements to satisfy the dependencies when they are executed in
>>> parallel by the 'forall' loop.
>>>
>>> Please share your views on such a programming model and correct me if
>>> I made any wrong assumptions in my explanation.
>>>
>>> If you find any interesting use cases in Chapel please share it.
>>>
>>> Regards,
>>>
>>> On Sat, Mar 5, 2016 at 6:15 PM, raghesh <[email protected]> wrote:
>>>>
>>>> Hi Chapel Team,
>>>>
>>>> I am a Post Graduate student at Indian Institute of Technology, Madras
>>>> (IIT
>>>> Madras). I would like to propose a project for Google Summer of Code this
>>>> year. I was a GSOC student during its 2011 version and contributed to
>>>> LLVM
>>>> Polly [1].
>>>>
>>>> My focus is on improving the productivity of parallel programs
>>>> (especially
>>>> OpenMP programs). In that regard we have published a paper titled "Unique
>>>> Worker model for OpenMP" [2], in ICS 2015, which facilitated placement of
>>>> barriers (#pragma omp barrier) within parallel-for-loops (#pragma omp
>>>> for).
>>>>
>>>> Now as GSOC project, I would like to introduce such a feature for the
>>>> 'forall' loops in Chapel, which is more or less similar to
>>>> parallel-for-loops in OpenMP.
>>>>
>>>> I am reasonably new to Chapel and started learning about the language
>>>> features.
>>>>
>>>> Please share your valuable thoughts on the project idea and any comments
>>>> on
>>>> this would be of great help.
>>>>
>>>>
>>>> [1] http://polly.llvm.org/
>>>> [2] http://dl.acm.org/citation.cfm?id=2751238
>>>>
>>>> Regards,
>>>> --
>>>> Raghesh Aloor
>>>> PhD Scholar
>>>> PACE Lab, Dept. of CSE, IIT Madras
>>>> http://www.cse.iitm.ac.in/~raghesh/
>>>
>>>
>>>
>>>
>>
>
>
>
> --
> Raghesh Aloor
> PhD Scholar
> PACE Lab, Dept. of CSE, IIT Madras
> http://www.cse.iitm.ac.in/~raghesh/
--
Raghesh Aloor
PhD Scholar
PACE Lab, Dept. of CSE, IIT Madras
http://www.cse.iitm.ac.in/~raghesh/
------------------------------------------------------------------------------
Transform Data into Opportunity.
Accelerate data analysis in your applications with
Intel Data Analytics Acceleration Library.
Click to learn more.
http://pubads.g.doubleclick.net/gampad/clk?id=278785231&iu=/4140
_______________________________________________
Chapel-users mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-users
