A implementação da linguagem multithreaded Cilk-5

A quinta versão da linguagem multithreaded Cilk utiliza um algoritmo de escalonamento "work-stealing" comprovadamente eficaz, semelhante ao primeiro sistema, mas a linguagem foi completamente redesenhada e o sistema de runtime completamente reengenheirado. A eficiência da nova implementação foi auxiliada por uma estratégia clara que surgiu a partir de uma análise teórica do algoritmo de escalonamento: concentrar-se na minimização de custos que contribuem para o trabalho, mesmo à custa de custos que contribuem para o caminho crítico. Embora possa parecer contra-intuitivo mover custos para o caminho crítico, este princípio de "trabalho primeiro" levou a uma implementação portátil do Cilk-5 em que o custo típico de gerar uma thread paralela é apenas entre 2 e 6 vezes o custo de uma chamada de função C em uma variedade de máquinas contemporâneas. Muitos programas Cilk rodam em um processador com praticamente nenhuma degradação em comparação com programas equivalentes em C. Este artigo descreve como o princípio de trabalho primeiro foi explorado no design do compilador do Cilk-5 e seu sistema de runtime. Em particular, apresentamos a nova estratégia de compilação "two-clone" do Cilk-5 e seu protocolo de exclusão mútua semelhante ao de Dijkstra para implementar a deque pronta no escalonador de trabalho-roubado.