llvm dev - Jul 2013 - [LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM backend code generation

-----Original Message-----
From: Shuxin Yang [mailto:shuxin.llvm at gmail.com] 
Sent: Wednesday, July 17, 2013 1:50 AM
To: Wan, Xiaofei
Cc: Evan Cheng; Shuxin Yang; LLVM Developers Mailing List (llvmdev at
cs.uiuc.edu)
Subject: Re: [LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM
backend code generation


On 7/16/13 7:23 AM, Wan, Xiaofei wrote:
> Yes, the purpose is similar, we started this job from last year; But 
> it Shuxin's solution is module based (correct me if I am wrong), we 
> tried this solution and failed for many reasons, it is described in my 
> design document 
> https://docs.google.com/document/d/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgj
> Y-vhyfySg/edit?usp=sharing
>
> we need discuss two solution and compare them, then adopt one solution
>
> The biggest difference of module based parallelism and function based 
> parallelism are 1. how to partition module into different pieces which 
> consume similar time, it is a difficult question
Why difficult?
> 2. How to make sure the generated binary is same each time
It depends on what is the same.  In the merged version, constant may keep one
copy, while in the partition version,  constant may be duplicated as the
post-IPO passes may generated some constant, and they cannot share with the same
constant generated in other partitions.

All these issues don't sound to be a problem in practice.
> 3. if 2 can't be achieved, it is difficult to validate the correctness 
> of parallelism
It is nothing about the correctness.

[Xiaofei] why? I don't understand it very well here, you mean it can
generate totally identical binaries as the original llc, including the function
order (function order may not affect code quality, but we should make sure the
output is same in each run)?

On 7/16/13 7:51 PM, Wan, Xiaofei wrote:
>
> -----Original Message-----
> From: Shuxin Yang [mailto:shuxin.llvm at gmail.com]
> Sent: Wednesday, July 17, 2013 1:50 AM
> To: Wan, Xiaofei
> Cc: Evan Cheng; Shuxin Yang; LLVM Developers Mailing List (llvmdev at
cs.uiuc.edu)
> Subject: Re: [LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM
backend code generation
>
>
> On 7/16/13 7:23 AM, Wan, Xiaofei wrote:
>> Yes, the purpose is similar, we started this job from last year; But
>> it Shuxin's solution is module based (correct me if I am wrong), we
>> tried this solution and failed for many reasons, it is described in my
>> design document
>> https://docs.google.com/document/d/1QSkP6AumMCAVpgzwympD5pI3btPJt4SRgj
>> Y-vhyfySg/edit?usp=sharing
>>
>> we need discuss two solution and compare them, then adopt one solution
>>
>> The biggest difference of module based parallelism and function based
>> parallelism are 1. how to partition module into different pieces which
>> consume similar time, it is a difficult question
> Why difficult?
>
>> 2. How to make sure the generated binary is same each time
> It depends on what is the same.  In the merged version, constant may keep
one copy, while in the partition version,  constant may be duplicated as the
post-IPO passes may generated some constant, and they cannot share with the same
constant generated in other partitions.
>
> All these issues don't sound to be a problem in practice.
>
>> 3. if 2 can't be achieved, it is difficult to validate the
correctness
>> of parallelism
> It is nothing about the correctness.
>
> [Xiaofei] why?
I'm not sure what you are asking here. Are you asking why partition 
still preserve correctness?
> I don't understand it very well here, you mean it can generate totally
identical binaries as the original llc,
I didn't say *totally* identical.  IPO with partition could be slightly 
different from the one without partition,
say the former may have duplicated constant in the .text section, which 
is totally acceptable in practice.
So long as partition remain unchanged, each time LTO+partition should 
yield same result.
> including the function order (function order may not affect code quality,
but we should make sure the output is same in each run)?
By "the same", which are involved in comparison:
    1. IPO w/ partition vs IPO wo/ partition,
    2. n-th run of IPO w/ partition n+1-th run of IPO w/partition

If 2) should show some difference, it means it has some bugs.

  If you are talking about 1), nobody can guarantee 1)  generate 
*totally* identical objections,
and I don't understand we have such esoteric need.

On 7/16/2013 9:51 PM, Wan, Xiaofei wrote:
> [Xiaofei] why? I don't understand it very well here, you mean it can 
> generate totally identical binaries as the original llc, including the 
> function order (function order may not affect code quality, but we 
> should make sure the output is same in each run)? 
Per <http://www-plan.cs.colorado.edu/diwan/asplos09.pdf>, function order 
can affect performance by up to 15%.

-- 
Joshua Cranmer
Thunderbird and DXR developer
Source code archæologist

Yes, sometime it may affect code layout which may affect performance;
theoretically it is better if we could generate totally identical code,
including function order, meanwhile, it is easy to validate whether parallelism
is correct, just compare the outputs simply

-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Joshua Cranmer ??
Sent: Wednesday, July 17, 2013 12:47 PM
To: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] [LLVM Dev] [Discussion] Function-based parallel LLVM
backend code generation

On 7/16/2013 9:51 PM, Wan, Xiaofei wrote:
> [Xiaofei] why? I don't understand it very well here, you mean it can 
> generate totally identical binaries as the original llc, including the 
> function order (function order may not affect code quality, but we 
> should make sure the output is same in each run)?
Per <http://www-plan.cs.colorado.edu/diwan/asplos09.pdf>, function order
can affect performance by up to 15%.

--
Joshua Cranmer
Thunderbird and DXR developer
Source code archæologist

_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev