From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 3E12CBCF1 for ; Thu, 18 Nov 2010 14:16:01 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AiMDACIJ5EzRVdW0k2dsb2JhbACBfZIkMoV2AYc2SwgWAQIJCQoJEQMfpVSJYoIYhRsuiFkBAQMFhUYEgVyIfIV7 X-IronPort-AV: E=Sophos;i="4.59,214,1288566000"; d="scan'208";a="79586519" Received: from mail-yx0-f180.google.com ([209.85.213.180]) by mail2-smtp-roc.national.inria.fr with ESMTP; 18 Nov 2010 02:00:10 +0100 Received: by yxj4 with SMTP id 4so1588416yxj.39 for ; Wed, 17 Nov 2010 17:00:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:cc:content-type; bh=G6owPuS3cUHDhIyW9s+vBocYmji/XQB7t0gwnviKetE=; b=up+x4FUqD1nuwiQUTPrnAdjed97/IjusQhMmOlV7IGHQ2wDY4ocdsW5BJrXmtQYzZT Xz/fVytpV6vaEg93/3pr5g3S2Yf3bHUbo0T+N2QLleAs5r7vb34nzzSDZ7gpR/T/qX6e /syFcz021bnxHuk5NPSdWlViuX1rlrwg4bbMg= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=UsnZ5MyLJLwFzXxYW6koJt9xM753Z2Q1TQnEqnlJvwvfIMx5mbcgZ+I0JjOuhiTUpk 4DI/Sh97hcZYx8+BVAhTR5en9pTk7hZ20zVnY81jSJZyhZh8mtQwIGarhIHOhQci2vvM m+wm1ZKLINlZkior8cVboB1dAJuuLMXZhEFT4= MIME-Version: 1.0 Received: by 10.90.27.14 with SMTP id a14mr3310aga.113.1290042009203; Wed, 17 Nov 2010 17:00:09 -0800 (PST) Received: by 10.91.154.3 with HTTP; Wed, 17 Nov 2010 17:00:09 -0800 (PST) In-Reply-To: References: <20101115182737.42b8dcae@loki.yggdrasil.draxit.de> <4CE228CA.3030503@gmail.com> <1289927042.16005.176.camel@thinkpad> <1289945605.16005.205.camel@thinkpad> <02be01cb860a$208f7aa0$61ae6fe0$@com> <20101117065011.GA2754@kerneis.info> <031301cb869c$8e33f120$aa9bd360$@com> Date: Thu, 18 Nov 2010 03:00:09 +0200 Message-ID: Subject: Re: [Caml-list] SMP multithreading From: Eray Ozkural To: Jon Harrop Cc: caml-list@yquem.inria.fr Content-Type: multipart/alternative; boundary=001636163d99b4325f0495494f41 X-Spam: no; 0.00; eray:01 ozkural:01 compiler:01 compiler:01 compilation:01 algebra:01 hpf:01 utils:01 computations:01 cheers:01 eray:01 ozkural:01 cheers:01 0200,:01 doable:01 --001636163d99b4325f0495494f41 Content-Type: text/plain; charset=ISO-8859-1 http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1650134 This is one of the more recent papers a quick search turns up, but you have to keep in mind that thread extraction is only one problem among many for a parallelizing compiler. I think the keyword you are looking for is "thread extraction". And here probably, it's the simplest kind of extraction... Food for some thought: assume that you have a very good compiler pass that extracts all possible threads in the sequential code, can you name any other problems the compiler must solve to achieve good performance? I can't talk at all about the project I worked on, but as I mentioned previously, familiarize yourself with the RAW project, it was similar in some respects to the project I worked in: http://groups.csail.mit.edu/cag/raw/ This should, at least a bit, dispel the illusion that parallelizing compilers are helpless when they confront C code. Reading the OS/400 book had opened my mind about OS design, perhaps reading about recent computer architecture research projects will open others' eyes about compilers, and how useful they really can be! Also, I believe there ought to be some textbooks about multi-core architectures and relevant compilation strategies, let me post it if I find a comprehensive reference. The dream compiler would have all the cool linear algebra capabilities of HPF + the more general/free-form kinds of parallelization strategies in recent compilers. Ok, so what you really want to do is, parallelize applications that can benefit from them. Not file utils or web browsers. If you are so curious, stuff like povray would be in the test suite. Sometimes the parallelizing compiler parallelizes computations that a programmer wouldn't bother due to program complexity, here a basic block, there a basic block, some pipelining communication/computation overlap there.... I think it's a safe bet to say that, with all the general lameness surrounding parallel programming languages, parallelizing compilers will be very important in the near future. Cheers, On Thu, Nov 18, 2010 at 2:28 AM, Eray Ozkural wrote: > Yes, actually. :P > > > On Wed, Nov 17, 2010 at 11:15 PM, Jon Harrop < > jonathandeanharrop@googlemail.com> wrote: > >> Can you cite any papers from this century? ;-) >> >> >> >> Cheers, >> >> Jon. >> >> >> >> *From:* Eray Ozkural [mailto:examachine@gmail.com] >> *Sent:* 17 November 2010 13:41 >> *To:* Eray Ozkural; Jon Harrop; caml-list@yquem.inria.fr >> >> *Subject:* Re: [Caml-list] SMP multithreading >> >> >> >> On Wed, Nov 17, 2010 at 8:50 AM, Gabriel Kerneis >> wrote: >> >> On Wed, Nov 17, 2010 at 06:27:14AM +0200, Eray Ozkural wrote: >> > As I said even in C good results can be achieved, I've seen that, so I >> > know it's doable with ocaml, just a difficult kind of compiler. The >> > functional features would expose more concurrency. >> >> Could you share a pointer to a paper describing this compiler? >> >> >> I can't reveal much, but just to point out that there are indeed more >> sophisticated compilers than gcc: >> http://www.research.ibm.com/vliw/compiler.html >> >> So, uh, there are compilers that turn loops into threads, and also >> parallelize independent blocks.... Both coarse-grain and fine-grain >> parallelization strategies in existing compiler research can be effectively >> applied to the multi-core architectures. In fact, some of the more advanced >> compilers (like that of the RAW architecture) must be able to target it >> already, but who knows. :) Just consider that most of the parallelization >> technology is language independent, they can be applied to any imperative >> language. So, would such a thing be able to work on ocaml generated >> binaries? Most definitely, I believe, it is in principle possible to start >> from the sequential binary and emit parallel code! >> >> Best, >> >> >> >> -- >> Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara >> http://groups.yahoo.com/group/ai-philosophy >> http://myspace.com/arizanesil http://myspace.com/malfunct >> > > > > -- > Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara > http://groups.yahoo.com/group/ai-philosophy > http://myspace.com/arizanesil http://myspace.com/malfunct > > -- Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara http://groups.yahoo.com/group/ai-philosophy http://myspace.com/arizanesil http://myspace.com/malfunct --001636163d99b4325f0495494f41 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=3D1650134
This is one of the more recent papers a quick search turns up, but you= have to keep in mind that thread extraction is only one problem among many= for a parallelizing compiler. I think the keyword you are looking for is &= quot;thread extraction". And here probably, it's the simplest kind= of extraction... Food for some thought: assume that you have a very good c= ompiler pass that extracts all possible threads in the sequential code, can= you name any other problems the compiler must solve to achieve good perfor= mance?

I can't talk at all about the project I worked on, but as I mention= ed previously, familiarize yourself with the RAW project, it was similar in= some respects to the project I worked in:
http://groups.csail.mit.edu/cag/raw/

This should, at least a bit, dispel the illusion that parallelizing com= pilers are helpless when they confront C code. Reading the OS/400 book had = opened my mind about OS design, perhaps reading about recent computer archi= tecture research projects will open others' eyes about compilers, and h= ow useful they really can be!

Also, I believe there ought to be some textbooks about multi-core archi= tectures and relevant compilation strategies, let me post it if I find a co= mprehensive reference.

The dream compiler would have all the cool li= near algebra capabilities of HPF + the more general/free-form kinds of para= llelization strategies in recent compilers.

Ok, so what you really want to do is, parallelize applications that can= benefit from them. Not file utils or web browsers. If you are so curious, = stuff like povray would be in the test suite. Sometimes the parallelizing c= ompiler parallelizes computations that a programmer wouldn't bother due= to program complexity, here a basic block, there a basic block, some pipel= ining communication/computation overlap there.... I think it's a safe b= et to say that, with all the general lameness surrounding parallel programm= ing languages, parallelizing compilers will be very important in the near f= uture.

Cheers,

On Thu, Nov 18, 2010 at 2:28 = AM, Eray Ozkural <examachine@gmail.com> wrote:
Yes, actually. :P


On Wed, Nov 17, 2010 at 11:15 PM, Jon Harrop &= lt;j= onathandeanharrop@googlemail.com> wrote:

Can you cite any papers from= this century? ;-)

=A0

Cheers,

Jon.

=A0

From: Eray Ozkural [mailto:examachine@gmail.com]
Sent: 17 November 2010 13:41
To: Eray Ozkural; Jon Harrop;= caml-list@yq= uem.inria.fr


Subject: Re: [Caml-list] SMP multithreading=

=A0

On Wed, Nov 17, 2010 at 8:50 AM, Gabriel Kerneis <kerneis@pps.jussieu.fr> wrote= :

On Wed, Nov 17, = 2010 at 06:27:14AM +0200, Eray Ozkural wrote:
> As I said even in C g= ood results can be achieved, I've seen that, so I
> know it's= doable with ocaml, just a difficult kind of compiler. The
> functional features would expose more concurrency.

Could you share a pointer to = a paper describing this compiler?


I can't reveal much, but just to point out that there are indeed more s= ophisticated compilers than gcc:
http://www.research.ibm.com/vliw/comp= iler.html=A0

So, uh, there are compilers that turn loops into threads, and also para= llelize independent blocks.... Both coarse-grain and fine-grain paralleliza= tion strategies in existing compiler research can be effectively applied to= the multi-core architectures. In fact, some of the more advanced compilers= (like that of the RAW architecture) must be able to target it already, but= who knows. :) Just consider that most of the parallelization technology is= language independent, they can be applied to any imperative language. So, = would such a thing be able to work on ocaml generated binaries? Most defini= tely, I believe, it is in principle possible to start from the sequential b= inary and emit parallel code!

Best,



--
Eray Ozkural, PhD candidate.=A0 Comp. Sci.= Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philo= sophy
http://myspace.= com/arizanesil http://myspace.com/malfunct




--
Eray Ozkural, PhD candidate.=A0 Comp= . Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai= -philosophy
http://myspace.= com/arizanesil http://myspace.com/malfunct




--
Eray Ozkura= l, PhD candidate.=A0 Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/g= roup/ai-philosophy
http://myspace.com/arizanesil= http://myspace.com/malfunct
--001636163d99b4325f0495494f41--