To wrap up this thread on chapel-users: I am moving the subsequent discussion
to chapel-developers list.
Vassily
On 03/19/16 17:25, raghesh wrote:
> 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/
>
>
>
------------------------------------------------------------------------------
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=278785351&iu=/4140
_______________________________________________
Chapel-users mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-users
