Tiago Cogumbreiro

O Irrepupável

Back to top

Sunday, January 03, 2010

OpenCL review

OpenCL is an open standard being created by the Khronos Group, pushed by Apple and AMD. This technology features data parallelism and task parallelism. It is supposed to target a varied range of devices, for example, there is an embedded profile for mobile devices. MacOS X 10.6 has support for OpenCL. There is support for Linux and Windows in x86 and x86-64 architectures via AMD.

OpenCL may be touted as being in relation to multicores as OpenGL is in relation GPUs. But in fact, OpenCL is a broader technology than OpenGL is, since it targets not only multicores but GPUs as well. Additionally, there is a tight coupling between both of these technologies, e.g. it is possible to share a buffer between an OpenCL operation and an OpenGL operation.

In OpenCL there is a concept of kernel that is akin to SIL places. A kernel consists of a C program whose entry point is a function. Kernels communicate via shared memory (buffers). A work-item is composed by one ore more kernels that are executed sequentially. Each kernel may be target of data parallelization. A work-item may be target of task parallelization. Work-items are executed on a device (e.g. a CPU, a GPU) that consists of one or more processing unit.

Technically kernels are C string that must be compiled every time the program loads. Notice that the OpenCL runtime may cache compilation.

The site HPC Wire published a very good insight from a person with experience with HPC (OpenMP in particular) “Compilers and More: OpenCL Promises and Potential” from which I would like to quote two paragraphs:

So, are OpenCL programs going to be performance portable or not? Sadly, not. [...] An optimized kernel for one device may or may not perform well on another, but is unlikely to be optimal for that second device.

The intent is apparently that OpenCL will support an ecosystem of tools, middleware and applications, not to be the portable parallel abstraction. Even though the kernels are not performance portable, even if you have to tune your kernels for each device, the ability to write your kernels for different devices in the same language is a great leap forward from where we are today.

References

Thursday, December 03, 2009

Revisão da linguagem Go

Podemos pensar no Go como um C mais limpo: estruturas (structs) como no C, libertação automática de memória (há garbage collection), referências (sem aritmética de ponteiros) e valores, funções e os tipos de dados usuais. As funções podem retornar tuplos, mas os tuplos não são valores de primeira-classe, i.e. não podem ser alocados ou guardados numa variável.

Exemplo de uma função que retorna um tuplo:

func foo(int v) (int v1, int v2) {
return v, v*2
}

a, b = foo(3);

Temos a palavra chave func, o nome da função foo, os parâmetros da função (int v) e os parâmetros de saída (int v1, int v2). É o regresso dos parâmetros de saída no sentido em que podemos manipulá-los, mas sintacticamente não estão ao lado dos parâmetros de entrada, o que me parece uma boa escolha. O mesmo exemplo pode ser reescrito assim (mais estranho na minha opinião):

func foo(int v) (int v1, int v2) {
v1 = v;
v2 = v * 2;
return;
}

a, b = foo(3);

Existem dois conceitos que merecem realce: métodos e interfaces. Os métodos são funções que se associam a um tipo de dados e são utilizados como os métodos do C++ ou do Java. Não podem ser associados a interfaces; podem ser associados tipos, por exemplo a uma estrutura. A definição de um método é isolada, não é feita na definição do tipo ao qual está associada.

Exemplo ilustrativo de um método que calcula a norma sobre o tipo de dados ponto:

// Disclairmer: o exemplo foi feito por mim sem testar se funciona
struct Point {
int x;
int y;
}

func (Point self) Magnitude() int {
return Math.sqrt(self.x * self.x + self.y * self.y)
}

Point p = Point{0, 0};
p.Magnitude(); // returns 0
p.x = 2;
p.Magnitude(); // returns 2

Resumindo, para definir um método temos a keyword func, entre parêntises o tipo ao qual o método vai estar associado e o nome da variável (neste caso usei self), de seguida os parâmetros e o tipo de retorno (ou parâmetros de saída). Um interface identifica (estruturalmente) tipos que tenham um dado conjunto de métodos associados. Ou seja, se dois valores tiverem pelo menos os mesmos métodos que um dado interface, então são considerados daquele interface. A associação a um dado interface é implicita, não existe associação, e.g. T1 implements ISomeInterface.

Concorrência

Existe paralelismo de tarefas, nesta linguagem é feita através de uma goroutine (semelhantes a threads ou tasks). As goroutines são (pretendem ser) leves. Para criar uma goroutine, colocamos a keyword go antes de uma chamada de uma função:

go LongComputation();

A comunicação entre tarefas parelelas é feita através de memória partilhada ou através de canais. Por exemplo, para criar um canal que transmite inteiros e associá-lo a uma variável c, faz-se:

c := make(chan int)

Podemos usar esse canal no exemplo seguinte em que criamos duas tarefas paralelas (goroutines) uma envia mensagem pelo canal c e a outra tarefa recebe mensagens pelo mesmo canal, mostrando o valor recebido no ecrã.

func client() {
  c<- 10;
}

func server() {
  for { // this for is equivalente to C's for (;;) 
    msg := <-c;
    fmt.Printf("received %d\n", msg);
  }
}

O select da linguagem é muito poderoso e podem fazer-se servidores/clientes mais complicados com brevidade. O seguinte exemplo está na especificação da linguagem.

var c, c1, c2 chan int;
var i1, i2 int;
select {
case i1 = <-c1:
 print("received ", i1, " from c1\n");
case c2 <- i2:
 print("sent ", i2, " to c2\n");
default:
 print("no communication\n");
}

for {  // send random sequence of bits to c
 select {
 case c <- 0:  // note: no statement, no fallthrough, no folding of cases
 case c <- 1:
 }
}

Num select com várias operações de recepção (<-c) e/ou de envio (c<-) de mensagem é tratada de cima para baixo o primeiro ramo que esteja activo. Caso não hajam expressões de envio/recepção de mensagem activas, é avaliado o caso default. Se o ramo default não estiver definido, então o select fica bloqueado até uma expressão de envio/recepção esteja activa. No exemplo acima, o primeiro select tenta receber uma mensagem pelo canal c1. Caso não haja mensagem para se receber no canal c1, o select tenta enviar uma mensagem pelo canal c2. Se não houver transmissão da mensagem, então é avaliado o ramo default e mostra-se no ecrã no communication. De seguida temos um select dentro de um ciclo, o Go alterna de uma forma uniforme e justa (não está provado) entre os vários ramos activos, enviando por este motivo ora o valor 1 ora o valor 0 pelo canal c.

Como os canais são valores, podem ser enviados através de um canal. Existe primitivas de comunicação síncrona e assíncrona. É possível tipificar canais, especificando o tipo de valores comunicado e se é de entrada ou de saída. Não há suporte para tipos de sessão.

Conclusão

O Go é vendida como uma linguagem de sistemas (concorrência incluida). Se me dessem para escolher C ou Go ignorando o contexto de utilização, escolheria Go sem piscar os olhos. Escolheria também Go ao invés do C++. Acho que tem uma elegância sintática razoável (para uma linguagem que segue a sintaxe do C) e que faz um bom compromisso nas primitivas e abstracções escolhidas: gosto muito do sistema de interfaces mas sinto falta de excepções.

A resposta à concorrência é insuficiente. Um slogan do Go é, e passo a citar:

Do not communicate by sharing memory; instead, share memory by communicating.

Mas entre o que se apela e o que se faz vai um grande passo. Por mais que existam canais e de existir o slogan, continua a ser possível trabalhar com memória partilhada sem qualquer protecção do sistema de tipos. Além disso comprometem-se com uma memória com um espaço global de endereços único, em contraste com um um espaço global de endereços particionado, não se preparando para sistemas mais esotéricos com modelos de memória diferentes. Para a omissão de excepções é dada a justificação que não é um problema bem resolvido, ignorando o bom trabalho desenvolvido na linguagem X10. Para a concorrência é feito o inverso: albergam ambos os idiomas e promovem timidamente a concorrência por passagem de mensagem.

Monday, November 16, 2009

Quick update

Time for a quick recap of what's been life like. I finished my masters on informatics, the thesis is online. The work is the formalization of a compiler from the π-calculus into a multithreaded TAL. I've learned a lot these past two years! Particularly in the value of (provable) specification for an algorithm.

On another front I have been working on Callas (which needs a big brush up on its site). Once again, I have been defining a translation function, this time from Callas (a functional, declarative language with modules) to a byte-code language based on Java (with some simplifications). I now have a more influent position and am giving some (small) input on the design of the language.

Meanwhile work has continued on the MIL. We have released a new version of the interpreter, which includes a deadlock checker. Technically this amounted to integrate the typechecker with a Prolog engine (we are using JLog).

Finally, I am eager for the acceptance of my PhD application in FCUL. The acceptance process usually takes one month (sigh), so I should know the results any time soon.

All in all things are working out smoothly ;-)

Thursday, July 02, 2009

An applet for MIL and the simply typed π-calculus compiler

In an effort to showcase my MSc work, I have developed an applet that contains the π-calculus compiler along with the MIL interpreter. You can try out either MIL our the simply-typed π-calculus and run it online. Our article about compiling the π-calculus into a multithreaded typed assembly language is an useful reference.

Try MIL and the pi-calculus compiler on-line!

The π-calculus consists of processes that run concurrently—you may read processes as tasks or threads, although they sit at a much higher level. The simplest process is the inactive one that finishes, we represent it by a zero 0. The basis of the π-calculus is communication; it is so important that the fundamental step of computation is the communication of sequences of values (integers, strings, and channels). Processes synchronize (and communicate) by message-passing, using channels. To send a message 10 through a channel x we write the output process x<10>. To receive a message through a channel x and store it in a name y that is visible in process P we write the input process x(y).P, notice that process P is not a variable, it must be replaced with an actual process, like the inactive process 0. If we want to receive a message repeatedly, like a server does, we just write a bang (!) in front of an input process, for example !x(y).P. To execute process P in parallel with process Q we write the parallel process P | Q, or to remove ambiguity we may use parenthesis (P | Q). To use a channel x in a process P, we must first declare it along with its type T by writing new x:T P. A type T is not a variable, it can be either an integer type int, a string type str, or a channel ^[T1,...,Tn] (the parameters ranging from T1,...,Tn are a possibly empty sequence of types, like the empty channel type ^[] or the channel that communicate two integers ^[int,int]. Channels may themselves send channels, for example channel type ^[int,^[int]] types channels that communicates two values, one of the integer type, another a channel that communicates integers.

A quick example of an echo server:

new echo:^[int,^[int]] (
  !echo(x,y).y<x>
  |
  new print:^[int] (
    !print(m).printInt<m>
    |
    echo<10,print>
  )
)

Tuesday, June 23, 2009

“Compiling the π-calculus into a multithreaded typed assembly language” is published

After one year the article I presented in PLACES '08 was published.

We extend a previous work on a multithreaded typed assembly language (MIL) targeted at shared memory multiprocessors, and describe the design of a type-preserving compiler from the π-calculus into MIL. The language enforces a policy on lock usage through a typing system that also ensures race-freedom for typable programs, while allowing for typing various important concurrency patterns. Our translation to MIL generates code that is then linked to a library supporting a generic unbounded buffer monitor, variant of Hoare's bounded buffer monitor, entirely written in MIL. Such a monitor shields client code (the π-calculus compiler in particular) from the hazardous task of direct lock manipulation, while allowing for the representation of π-calculus channels. The compiler produces type correct MIL programs from type correct source code, generating low-contention cooperative multithreaded programs.

Tiago Cogumbreiro, Francisco Martins, and Vasco T. Vasconcelos. Compiling the π-calculus into a multithreaded typed assembly language. ENTCS, 241:57–84, 2009.

Monday, April 06, 2009

Problemas com acentos usando Latex, Flyspell, ISpell e Emacs

Estive muito tempo com problemas na forma como o Emacs e o ISpell reconheciam as palavras portuguesas. Depois de muito escavar lá encontrei o .emacs do sítio oficial do dicionário português para ISpell. Para corrigir, coloquem este código no vosso .emacs:

(custom-set-variables
   '(ispell-local-dictionary-alist
     (quote (("portugues" "[A-Za-zàèìòùÀÈÌÒÙáéíóúÁÉÍÓÚãõÃÕâêîôûÂÊÎÔÛçÇ]"
                          "[^A-Za-zàèìòùÀÈÌÒÙáéíóúÁÉÍÓÚãõÃÕâêîôûÂÊÎÔÛçÇ]"
                          "[-]" nil nil "~latin1" iso-8859-1)
             ("portutex"  "[A-Za-z\\\\\\\\]"
                          "[^A-Za-z\\\\\\\\]"
                          "[---~`'^{}]" nil nil "~tex" iso-8859-1)))))

Isto é quase arte ASCII.

Wednesday, April 01, 2009

Redirecting to an external link/URL in Zope (and Plone)

Go to the Zope Management Interface. In Plone click on Site Setup (on the upper left corner) and then under Plone Configuration click on Zope Management Interface.

Next, create a content Script (Python) (select it in the drop-down widget in the upper left corner of the page). Select the name of the link of the origin of the redirection and click on Add and Edit.

Add the following content:

# Import a standard function, and get the HTML request and response objects.
from Products.PythonScripts.standard import html_quote
request = container.REQUEST
RESPONSE = request.RESPONSE

#return context.REQUEST.RESPONSE.redirect("http://www.google.com/")
return RESPONSE.redirect("http://www.google.com/")

This will redirect http://YOURHOSTNAME/foo (if you create the python script at the root of your Zope Management Interface named foo) and redirect it to http://www.google.com/. Could be easier (and fully accessible trough Plone's UI).

Sunday, March 08, 2009

MiNEMA Winter School 2009

I am going to attend MiNEMA Winter School. Great oportunity to learn about wireless sensor networks and to discover Göteborg.

Wednesday, February 18, 2009

World of Goo

I was amazed by the demo and had to buy the full game of World of Goo (for Linux). I do not play a game in years, so this was really a urge I could not control ;-) The game cost me 16 euros.

Wednesday, February 04, 2009

Hindley/Milner Type Inference Algorithm implementated in Haskell (untested and naïve)

I do not program in Haskell in a couple of years. Today I needed to learn the Hendley/Milner algorithm for type inference and decided to implement it in Haskell. A far more interesting related blog post is one about “Writing A Lisp Interpreter In Haskell”, by Slava Akhmechet.

You can grab the (hardly tested) code, released under public domain, in Pastebin at http://pastebin.com/f7dede189. The Source Code Is The Documentation™.

I can't stress enough the usefulness of algebraic data types and declarative languages for creating compilers. But alas, I am still working with Java in my research projects.

Update: Because I have somehow broken the indentation, I have taken the chance to re-upload the source code, while cleaning up some code. Added a nice link about interpreter implementation using Haskell.