Transcript
Page 1: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

Guido Araujo (IC-UNICAMP)email: [email protected]

Alexandro Baldassin (IGCE-UNESP) email: [email protected]

Blue Gene/Q

Programação Paralela usando Memórias Transacionais: da

Academia à Indústria

IV Escola Regional de Alto Desempenho de São Paulojulho de 2013

Page 2: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

2

Roteiro

• Parte 1 • Programação paralela na atualidade• Transações: uma estratégia otimista• Modelo de execução

• Parte 2• Arquitetura básica de uma STM

• Exemplo usando o GCC• Arquitetura básica de uma HTM

• IBM BlueGene Q

Page 3: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

PARTE 1Introdução e Conceitos Básicos

Page 4: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

Sistema de memória compartilhada

c0 c1 c2 c3

counter

temp

store (counter, temp)

temp

load (temp, counter)

• Usado como modelo de execução de Pthreads e OpenMP

Page 5: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

5

Memória Compatilhada

• Processo cria várias threads de execução• Threads compartilham espaço de endereçamento• Comunicação é feita diretamente através de leituras e

escritas em memória compartilhada • Acessos concorrentes de leitura e escrita podem causar

inconsistências (condições de corrida)• Sincronização é usada para evitar tais cenários

Page 6: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

6

Sincronização

• Evitar intercalações inconsistentes de execução

shared counter;void work(){ counter++;}

Qual o resultado esperado após a primeira execução?

shared counter;void work(){ counter++;}

Page 7: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

7

Sincronização

• Evitar intercalações inconsistentes de execução

shared counter;void work(){ counter++;}

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

Page 8: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

8

Sincronização

• Evitar intercalações inconsistentes de execução

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

t1 (counter++) t2 (counter++)

Page 9: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

9

Sincronização

• Evitar intercalações inconsistentes de execução

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

t1 (counter++) t2 (counter++)

Page 10: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

10

Sincronização

• Evitar intercalações inconsistentes de execução

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

t1 (counter++) t2 (counter++)

O que ocorreu aqui?

Page 11: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

11

Sincronização

• Evitar intercalações inconsistentes de execução

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

t1 (counter++) t2 (counter++)

Qual o valor lido?

Page 12: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

12

Sincronização

• Evitar intercalações inconsistentes de execução

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

t1 (counter++) t2 (counter++)

Page 13: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

13

Sincronização

• Evitar intercalações inconsistentes de execução

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

t1 (counter++) t2 (counter++)

Page 14: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

14

Sincronização

• Evitar intercalações inconsistentes de execução

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

t1 (counter++) t2 (counter++)

Page 15: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

15

Sincronização

• Evitar intercalações inconsistentes de execução

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);

t1 (counter++) t2 (counter++)

Está correto?

Page 16: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

16

Mecanismos de Sincronização

• Bloqueantes• travas (locks)• variáveis de condição (condition variables)• semáforos/monitores

• Não-bloqueantes• livre de espera (wait-free)• livre de trava (lock-free)• livre de obstrução (obstruction-free)

Page 17: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

17

Exemplo

• Considere o seguinte problema: implementar uma lista de inteiros ordenados em ordem crescente, admitindo operações como inserção, remoção e consulta

• Esta tarefa pode ser desenvolvida facilmente por alunos de disciplinas de introdução à computação

• Desejamos uma versão paralela, que permita operações concorrentes na lista.

Page 18: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

18

Lista ordenada – sequencial

class Node { int key; Node next;}

class List { private Node head; public List() { head = new Node(Integer.MIN_VALUE); head.next = new Node(Integer.MAX_VALUE); }}

Page 19: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

19

Lista ordenada – sequencial

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

a chead tail

Page 20: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

20

Lista ordenada – sequencial

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

a chead tail

pred curr

add(b)

Page 21: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

21

Lista ordenada – sequencial

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

a chead tail

pred curr

add(b)

Page 22: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

22

Lista ordenada – sequencial

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

a chead tail

pred curr

b

add(b)

Page 23: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

23

Lista ordenada – sequencial

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

a chead tail

pred curr

b

add(b)

Page 24: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

24

Lista ordenada – sequencial

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

a chead tail

pred curr

b

add(b)

Page 25: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

25

Lista ordenada – sequencial

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

a chead tail

pred curr

b

public boolean remove(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item == curr.key) { pred.next = curr.next; return true; } else return false;}

a b chead tail

pred curr

remove(b)

Page 26: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

26

Paralelizando

• Como desenvolver uma versão paralela do exemplo anterior?

• Sendo otimista• Operações de inserção, remoção e busca podem

“potencialmente” ser executadas em paralelo

a b chead tail

d f

Thread 1remove(d)

Thread 2search(b)

Page 27: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

27

Paralelizando

• Como desenvolver uma versão paralela do exemplo anterior?

• Sendo otimista• Operações de inserção, remoção e busca podem

“potencialmente” ser executadas em paralelo

• Mais seguro• Ser pessimista e assumir que sempre haverá conflitos• Lock global

Page 28: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

28

Lista ordenada – lock global

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

Page 29: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

29

Lista ordenada – lock global

public boolean add(int item) { Node pred, curr;

pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; return true; } else return false;}

public boolean add(int item) { Node pred, curr; boolean valid = false;

lock.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; valid = true; } lock.unlock(); return valid;}

Page 30: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

30

Lista ordenada – lock global

• Ideia do lock global• Antes de iniciar o trecho de código que altera a lista, adquirir a

trava (lock)• Após trecho de código, liberar a trava (unlock)• Funciona?

• Solução simples, mas não escala!• Operações são serializadas

Page 31: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

31

Serializandopublic boolean add(int item) { Node pred, curr; boolean valid = false;

lock.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; valid = true; } lock.unlock(); return valid;}

public boolean add(int item) { Node pred, curr; boolean valid = false;

lock.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; valid = true; } lock.unlock(); return valid;}

• Como melhorar a solução?• Sugestões?

Page 32: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

32

Lista ordenada – locks finos

• Ideia• Associar um lock a cada nó da lista• Antes do conteúdo do nó ser acessado, adquirimos seu respectivo

lock (liberando-o após o acesso)

• Essa abordagem funciona?• Considere duas operações concorrentes para remoção dos itens

‘b’ e ‘a’, por duas threads distintas (T1 e T2)

Page 33: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

33

Lista ordenada – locks finos

a b chead tail

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

T1

Page 34: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

34

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

pred curr

a b chead tail

T1

Page 35: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

35

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

pred curr

a b chead tail

T1

Page 36: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

36

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

pred curr

a b chead tail

T1

Page 37: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

37

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

pred curr

a b chead tail

T1

Assuma um “page fault” aqui!!

Page 38: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

38

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

pred curr

a b chead tail

remove(a) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

T1 T2

Page 39: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

39

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

pred curr

a b chead tail

remove(a) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

pred curr

T1 T2

Page 40: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

40

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

pred curr

a b chead tail

remove(a) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

pred curr

T1 T2

Thread azul volta

Page 41: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

41

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

pred curr

a b chead tail

remove(a) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

pred curr

T1 T2

Resultado?

Page 42: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

42

remove(b) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

Lista ordenada – locks finos

a b chead tail

remove(a) ... head.lock(); pred = head; curr = pred.next; while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; pred.lock(); } if (item == curr.key) { pred.next = curr.next; valid = true; } pred.unlock(); return valid;}

T1 T2

“a” ainda ficou!!

Page 43: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

43

Lista ordenada – locks finos

• Antes de alterar um nó, uma thread necessita adquirir as travas para o nó atual e o próximo

• Note que as threads envolvidas precisam adquirir os locks na mesma ordem para evitar o risco de deadlock

• Não é trivial provar a corretude!

• Exemplo de código para a operação de inserção ...

Page 44: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

44

Lista ordenada – locks finos

public boolean add(int item) { boolean valid = false; head.lock(); Node pred = head; Node curr = pred.next; curr.lock(); while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } if (item != curr.key) { Node newNode = new Node(item); newNode.next = curr; pred.next = newNode; valid = true; } curr.unlock(); pred.unlock(); return valid;}

Page 45: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

45

Lista ordenada – locks finos

public boolean add(int item) { boolean valid = false; head.lock(); Node pred = head; Node curr = pred.next; curr.lock(); while (curr.key < item) { pred.unlock(); pred = curr; curr = curr.next; curr.lock(); } if (item != curr.key) { Node newNode = new Node(item); newNode.next = curr; pred.next = newNode; valid = true; } curr.unlock(); pred.unlock(); return valid;}

Grande parte do código é específico para sincronização (6 de 18 linhas = ~33%)

Page 46: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

46

Problemas com lock finos

• Risco alto de deadlock• Diferentes locks adquiridos em diferentes ordens

• Operações lock e unlock custosas• Geralmente envolvem alguma forma de syscall

• Dificuldade relacionada a engenharia de software• Como encapsular um método com locks?• Como compor código?

Page 47: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

47

Composição de código com locks

• Imagine que nossa aplicação precise utilizar as operações da lista ligada para implementar uma outra operação de nível mais alto, como mover um elemento de uma lista para outra

• Não temos acesso ao código fonte• Apenas sabemos que cada operação é atômica

public boolean move(List new, List old, int item) { old.remove(item); new.add(item);}

Page 48: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

48

Composição de código com locks

• Imagine que nossa aplicação precise utilizar as operações da lista ligada para implementar uma outra operação de nível mais alto, como mover um elemento de uma lista para outra

• Não temos acesso ao código fonte• Apenas sabemos que cada operação é atômica

public boolean move(List new, List old, int item) { old.remove(item); new.add(item);}

Atômico?

Page 49: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

49

Composição de código com locks

• Colocar um lock global?public boolean move(List from, List to, int item) { newlock.lock(); from.remove(item); to.add(item); newlock.unlock();}

Funciona?

E se ocorrer busca(item,from) em outra thread neste ponto?

Page 50: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

50

Composição de código com locks

• Colocar um lock global?

• Esta solução requer que todas as operações atômicas da lista sejam envoltas pelo novo lock

• Uma solução alternativa seria quebrar o encapsulamento e expor a implementação da lista (quais locks foram usados)

public boolean move(List from, List to, int item) { newlock.lock(); from.remove(item); to.add(item); newlock.unlock();}

Page 51: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

51

Composição de código com locks

• Cada lista expõe seu lock global

• Esta solução funciona?

public boolean move(List from, List to, int item) { from.lock(); to.lock(); from.remove(item); to.add(item); from.unlock(); to.unlock();}

Page 52: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

52

Composição de código com locks

• Cada lista expõe seu lock global

• Esta solução funciona?

public boolean move(List from, List to, int item) { from.lock(); to.lock(); from.remove(item); to.add(item); from.unlock(); to.unlock();}

move(lista_clientes, lista_devedores, USER1);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

move(lista_devedores, lista_clientes, USER2);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

Thread 1 Thread 2

Page 53: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

53

Composição de código com locks

• Cada lista expõe seu lock global

• Esta solução funciona?

public boolean move(List from, List to, int item) { from.lock(); to.lock(); from.remove(item); to.add(item); from.unlock(); to.unlock();}

move(lista_clientes, lista_devedores, USER1);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

move(lista_devedores, lista_clientes, USER2);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

Thread 1 Thread 2

Page 54: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

54

Composição de código com locks

• Cada lista expõe seu lock global

• Esta solução funciona?

public boolean move(List from, List to, int item) { from.lock(); to.lock(); from.remove(item); to.add(item); from.unlock(); to.unlock();}

move(lista_clientes, lista_devedores, USER1);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

move(lista_devedores, lista_clientes, USER2);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

Thread 1 Thread 2

Page 55: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

55

Composição de código com locks

• Cada lista expõe seu lock global

• Esta solução funciona?

public boolean move(List from, List to, int item) { from.lock(); to.lock(); from.remove(item); to.add(item); from.unlock(); to.unlock();}

move(lista_clientes, lista_devedores, USER1);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

move(lista_devedores, lista_clientes, USER2);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

Thread 1 Thread 2

Page 56: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

56

Composição de código com locks

• Cada lista expõe seu lock global

• Esta solução funciona?

public boolean move(List from, List to, int item) { from.lock(); to.lock(); from.remove(item); to.add(item); from.unlock(); to.unlock();}

move(lista_clientes, lista_devedores, USER1);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

move(lista_devedores, lista_clientes, USER2);

from.lock();to.lock();from.remove(USER1);to.add(USER1);from.unlock();to.unlock();

Thread 1 Thread 2

DEADLOCK

Page 57: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

57

Programação concorrente

Complexidade

Des

empe

nho

Lock global

Page 58: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

58

Programação concorrente

Complexidade

Des

empe

nho

Lock global

Locks finos

Lock-free

Page 59: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

59

Programação concorrente

Complexidade

Des

empe

nho

Lock global

Locks finos

Lock-free

STM

HTM

TM

Page 60: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

60

Memória Transacional (TM)

X1 X2

i1: temp1 = load(counter);i2: temp1 = temp1 + 1;

i3: store(counter, temp1);

i1: temp2 = temp1;i2: temp2 = temp2 + 1;

i3: store(counter, temp2);

RAW

1 antes de 2

SUCESSO!!

Page 61: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

61

Memória Transacional (TM)

X1 X2

i1: temp1 = load(counter);i2: temp1 = temp1 + 1;

i3: store(counter, temp1);

i1: temp2 = temp1;i2: temp2 = temp2 + 1;

i3: store(counter, temp2);

2 antes de 1

ABORTA!!

RAW

Page 62: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

62

Memória Transacional (TM)

• No modelo transacional, programadores usam o conceito de transação como abstração• Atomicidade• Consistência• Isolamento

• Vantagens• Nível de abstração maior• Potencial ganho de desempenho

• Dependente de implementação (visto mais adiante)• Composição de código

Page 63: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

63

Memória Transacional (TM)

• No modelo transacional, programadores usam o conceito de transação como abstração• Atomicidade• Consistência• Isolamento

• Vantagens• Nível de abstração maior• Potencial ganho de desempenho

• Dependente de implementação (visto mais adiante)• Composição de código

Detalhes de como realizar a sincronização são movidos do programador para o sistema de execução

Page 64: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

64

Programando com TM

• Programador delimita a região que deve ser executada atomicamente• Exemplo com lista ligada

• Sistema de execução (pode ser hardware ou software) cuida de garantir atomicidade, isolamento e consistência

public boolean add(int item) { Node pred, curr; boolean valid = false;

atomic { pred = head; curr = pred.next; while (curr.key < item) { pred = curr; curr = curr.next; } if (item != curr.key) { Node node = new Node(item); node.next = curr; pred.next = node; valid = true; } } if (valid) return true; return false;}

Page 65: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

65

TM e composição de código

• O modelo transacional permite composição de código de forma natural• Aninhamento de transações

atomic { … atomic { … } …}

Page 66: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

66

TM e composição de código

• O modelo transacional permite composição de código de forma natural• Aninhamento de transações

• Exemplo anterior para mover elementos entre listaspublic boolean move(List new, List old, int item) { atomic { old.remove(item); new.add(item); }}

atomic { … atomic { … } …}

Page 67: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

67

Bom para quê?

• Estruturas de dados cuja escalabilidade é ruim com abordagens baseadas em locks• Exemplo: árvore rubro-negra

• Aplicações nas quais o uso de lock é muito conservativo

• Aplicações irregulares (uso extensivo de ponteiros)• Algoritmos de grafos

• Exemplo de sistema grande de porte• Servidor do jogo Quake (Zyulkyarov et al.)

Page 68: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

68

Implementação

• O mecanismo transacional precisa fornecer…

• Versionamento de dados• Os dados temporários (especulativos) usados pela transação

precisam ser mantidos em algum local• Essencial para garantiar atomicidade e consistência

• Isolamento da execução• É necessário um mecanismo para detectar e resolver os conflitos

entre transações

Page 69: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

69

Versionamento de dados

• Imediato (eager/pessimistic/direct)• Memória compartilhada atualizada imediatamente (valor

antigo armazenado em buffer)• Efetivação rápida, mas cancelamento lento

• Deferido (lazy/optimistic/deferred)• Armazena atualização em buffer interno• Cancelamento rápido, mas efetivação lenta

Page 70: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

70

Versionamento imediato

Page 71: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

71

Versionamento imediato

Page 72: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

72

Versionamento imediato

Page 73: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

73

Versionamento imediato

Page 74: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

74

Versionamento deferido

Page 75: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

75

Versionamento deferido

Page 76: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

76

Versionamento deferido

Page 77: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

77

Versionamento deferido

Page 78: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

78

Isolamento da execução

• Detecção de conflitos• Usa-se dois conjuntos:

• Read set: dados lidos • Write set: dados escritos

• Conflito se há intersecção entre o conjunto de leitura e escrita de transações diferentes

• Resolução de conflitos• Depende do gerenciador de contenção• Exemplo: abortar imediatamente, esperar, ...• Importante para garantir progresso

Page 79: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

79

Formas de detecção de conflitos

• Adiantado (eager/pessimistic/encounter-time)• Ocorre no momento dos acessos ao dados• Pode evitar executar código desnecessário• Mais suscetível a livelock

• Tardio (lazy/optimistic/commit-time)• Ocorre na efetivação da transação• Potencialmente menos conflitos• Menos suscetível a livelock, porém starvation pode ser

um problema

Page 80: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

80

Detecção de conflitos adiantado

Page 81: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

81

Detecção de conflitos adiantado

Page 82: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

82

Detecção de conflitos adiantado

Page 83: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

83

Detecção de conflitos adiantado

Page 84: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

84

Detecção de conflitos tardio

Page 85: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

85

Detecção de conflitos tardio

Page 86: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

86

Detecção de conflitos tardio

Page 87: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

87

Detecção de conflitos tardio

Page 88: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

PARTE 2Implementação em STM e HTM

Page 89: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

89

Implementação de TM

• O suporte transacional pode ser realizado em hardware, software ou uma mescla de ambos (híbrido)

• Hardware (HTM)• Melhor desempenho• Problemas com virtualização (espaço, tempo)

• Software (STM)• Desempenho depende muito da aplicação• Extremamente flexível• Ideal para testar novas ideias

Page 90: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

90

STM – Suporte

• Interface• API básica

• start, commit, barreiras de leitura e escrita• Object vs word

• Duas formas principais de implementação• Non-blocking• Blocking

• As implementações possuem diferentes garantias de progresso e consistência

Page 91: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

91

STM – Shavit & Touitou (1995)

PODC’95

Page 92: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

92

STM – Shavit & Touitou (1995)

• Cunhou o termo “software transactional memory” (STM)

• Transações eram “estáticas”• Uma transação precisa especificar, de forma antecipada, um vetor

com as posições de memória que serão acessadas

• Basicamente um CAS múltiplo

• A implementação, non-blocking, influenciou as novas propostas que surgiriam em seguida

Page 93: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

93

DSTM – Herlihy et al. (2003)

PODC’03

Page 94: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

94

DSTM – Herlihy et al. (2003)

• Definitivamente desencadeou a pesquisa em STM (junto com Harris & Fraser – OOPSLA 2003)

• Granularidade: objetos

• Detecção de conflitos adiantada/versionamento deferido

• Implementação é obstruction-free• Gerenciador de contenção é responsável por garantir progresso

Page 95: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

95

Rob Ennals (2005, 2006)

• Motivado pelo baixo desempenho de implementações non-blocking, Rob Ennals propôs implementar sistemas STM baseados em locks

• Efficient Software Transactional Memory (2005)• “This paper described how software transactional memory could be made more efficient if

one was prepared to sacrifice non-blocking properties. It was rejected from SPAA, but was widely circulated and was fairly influential on the design of subsequent STM implementations.”

• Software Transactional Memory Should Not Be Obstruction-Free (2006)

• “This paper was submitted to SCOOL 2005, but was deemed to be "too controversial for publication" and so was instead made the topic of a panel instead.”

Page 96: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

96

Lock-based STMs

• A ideia de Ennals gerou bastante controvérsia• Até então acreditava-se que as implementações deveriam ser non-

blocking por questões de garantia de progresso

• Ennals argumentou que o sistema runtime de linguagens modernas podem controlar o escolamento das threads, evitando o problema de preempção

• As principais implementações (mais rápidas) de STM atuais são blocking

Page 97: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

97

TL2 – Dice et al. (2006)

DISC’06

Page 98: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

98

TL2 – Dice et al. (2006)

• Principal representante de uma classe de implementações que adotam locks

• Granularidade: principalmente palavras

• Locks para escrita adquiridos durante fase de commit

• Versionamento deferido

• Relógio global é usado para manter consistência

Page 99: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

99

TL2 – Interface

• API• StartTx(), CommitTx(), AbortTx()• ReadTx(), WriteTx()

• Exemplo:

void PushLeft(DQueue *q, int val) { QNode *qn = malloc(sizeof(QNode)); qn->val = val; do { StartTx(); QNode *leftSentinel = ReadTx(&(q->left)); ... WriteTx(&(oldLeftNode->left), qn); } while (!CommitTx());}

Page 100: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

100

TL2 – Interface

• API• StartTx(), CommitTx(), AbortTx()• ReadTx(), WriteTx()

• Exemplo:

void PushLeft(DQueue *q, int val) { QNode *qn = malloc(sizeof(QNode)); qn->val = val; do { StartTx(); QNode *leftSentinel = ReadTx(&(q->left)); ... WriteTx(&(oldLeftNode->left), qn); } while (!CommitTx());}

Lembrando que potencialmente o compilador gera esse código a partir de blocos atômicos

Page 101: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

101

TL2 – Metadados

Compartilhado

GCLOCK

Ownership Record Table (ORT)Global Clock

..

. versionedlocks

Page 102: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

102

TL2 – Metadados

Compartilhado

GCLOCK

Ownership Record Table (ORT)Global Clock

..

. versionedlocks

Sempre incrementado (+2) quando uma transação é efetivada

Page 103: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

103

TL2 – Metadados

Compartilhado

GCLOCK

Ownership Record Table (ORT)Global Clock

..

. versionedlocks

Toda posição de memória acessada transacionalmente é mapeada para um registro (versioned lock) nessa tabela através de uma função hash

Page 104: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

104

TL2 – Metadados

Compartilhado

GCLOCK

Ownership Record Table (ORT)Global Clock

versionedlocks..

.

versão da palavra (se lock bit ==0) ouendereço da transação que travou registro

lock bit

Page 105: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

105

TL2 – Metadados

Privado

descritor transação (txdsc)

status versão

conjunto de leitura (cjtLeitura)

conjunto de escrita (cjtEscrita)

endereço

endereçovalor

Ativa,Abortada,Efetivada

Page 106: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

106

TL2 – Funcionamento

GCLOCK

descritor transação (txdsc)

status versão

conjunto de leitura (cjtLeitura)

conjunto de escrita (cjtEscrita)

endereço

endereçovalor

StartTx()1. txdsc.versao <- GCLOCK2. txdsc.status <- ACTIVE

Page 107: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

107

TL2 – Funcionamento

GCLOCK

descritor transação (txdsc)

status versão

conjunto de leitura (cjtLeitura)

conjunto de escrita (cjtEscrita)

endereço

endereçovalor

WriteTx(endereco, valor)1. cjtEscrita.insere(endereco, valor)

Page 108: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

108

TL2 – Funcionamento

GCLOCK

descritor transação (txdsc)

status versão

conjunto de leitura (cjtLeitura)

conjunto de escrita (cjtEscrita)

endereço

endereçovalor

..

.

ORT

ORT-address = hash(endereço)

ReadTx(endereco, valor)1. se (endereco em cjtEscrita) retorna cjtEscrita[endereco].valor2. v1 = ORT[hash(endereco)]3. valor = memoria[endereco]4. v2 = ORT[hash(endereco)]5. se (v1.lock travado || v1 != v2 || v1.versao > txdsc.versao)6. aborta transacao 7. cjtLeitura.insere(endereco)8. retorna valor

Page 109: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

109

TL2 – Funcionamento

GCLOCK

descritor transação (txdsc)

status versão

conjunto de leitura (cjtLeitura)

conjunto de escrita (cjtEscrita)

endereço

endereçovalor

..

.

ORT

ORT-address = hash(endereço)CommitTx(endereco, valor)1. trava elementos em CjtEscrita2. incrementa GCLOCK (+2)3. valida CjtLeitura4. atualiza memória com valores no CjtEscrita5. destrava CjtEscrita e atualiza versao na ORT

Memória Compartilhada

Page 110: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

110

TL2 – Características

• Contenção em GCLOCK pode ser tornar crítico para um número muito grande de transações concorrentes

• Implementação cuidadosa• Deve evitar deadlock

• Commit-time locking (CTL) com versionamento tardio• Conflitos write-after-write (WAW) e read-after-write (RAW)

detectados de forma tardia

Page 111: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

111

Novas lock-based STMs

• A maioria das STMs que surgiram depois usam o mesmo conceito de relógio global para garantir consistências (time-based STMs)

• Principais variações• Encounter-time locking (ETL) com versionamento tardio ou

adiantado, com extensão de versões• Tipos de conflitos (read-after-write, write-after-write) tratados de

formas diferentes

• Exemplos de STMs da mesma classe• TinySTM, SwisSTM

Page 112: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

112

Críticas sobre STMs

Comm. ACM’08

Queue’08

Page 113: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

113

Research toy

Page 114: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

114

STM strikes back

Comm. ACM’11

Page 115: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

115

STM strikes back

Comm. ACM’11

Autores argumentam que artigo anterior usou conjunto de aplicações/hardware inadequado

Page 116: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

116

STM strikes back

Page 117: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

117

Suporte transacional no GCC 4.7

• Suporte experimental a TM existe no GCC a partir da versão 4.7 (abril de 2012)• As construções adicionadas à linguagem são baseadas no

documento “Draft Specification of Transactional Language Constructs for C++”, versão 1.1

• http://gcc.gnu.org/wiki/TransactionalMemory

“The support is experimental. In particular, this also means that several parts of the implementation are not yet optimized. If you observe performance that is lower than expected, you should not assume that transactional memory is inherently slow; instead, please just file a bug.”

Page 118: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

118

Construções GCC

• Principais construções• __transaction_atomic {…}• __transaction_relaxed {…}• __transaction_cancel

• Anotações• __attribute__((transaction_safe))• __attribute__((transaction_pure))

• Opção -fgnu-tm deve ser passada ao compilador

Page 119: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

119

Exemplo com GCC – lista ligada

int list_add(list_node_t *head, int item){ list_node_t *pred, *curr;

__transaction_atomic { pred = head; curr = head->next; while (curr->key < item) { pred = curr; curr = curr->next; }

list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t)); node->key = item; node->next = curr; pred->next = node; } return 1;}

Demais operações implementadas da mesma forma

Page 120: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

120

Teste de “stress” da listavoid *list_exercise(void *arg){ int operations = (int)arg;

int add_or_remove, chance, value, last_value = 0; add_or_remove = 1; /* 1 - add, 0 - remove */ while (operations--) { chance = (int)(erand48(seed)*100); value = (int)(erand48(seed)*RANGE*2);

if (chance <= UPD_RATE) { if (add_or_remove) { list_add(linked_list, value); last_value = value; } else list_remove(linked_list, last_value); add_or_remove ^= 1; } else list_contain(linked_list, value);}

Todas as threads executam a mesma rotina

Page 121: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

121

Resultados “informais”

• Máquina: AMD Opteron• Taxa de atualização (UPD_RATE): 20%• Tamanho do conjunto: 100 elementos

1 2 4 80

2

4

6

8

10

12

14

16

18

Threads

Tem

po (s

)

Page 122: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

122

Compondo código usando TM

• Movendo elemento de uma lista para outra

• Se list_remove e list_add forem definidos em outro arquivo, é necessário usar transaction_safe

void move(list_node_t *from, list_node_t *to, int val){ __transaction_atomic { if (!list_remove(from, val)) __transaction_cancel; list_add(to, val); }}

__attribute__((transaction_safe)) int list_add(list_node_t *head, int item);

Page 123: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

123

Detalhes da geração e execução

• O compilador gera duas versões para cada rotina especificada com o atributo transaction_safe• A versão transacional é usada quando a rotina é chamada dentro

de uma transação

• O código gerado é linkado com uma biblioteca de runtime chamada libitm• Essa biblioteca pode ser substituída em tempo de execução

• Permite que diferentes implementações possam ser avaliadas de forma simples

• Especificação segue basicamente a ABI proposta pela Intel• Intel Transactional Memory Compiler and Runtime Application Binary

Interface, revisão 1.1 – maio de 2009

Page 124: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

124

HTM – Suporte

• Interface• Conjunto de instruções do processador• Exemplo: Intel TSX

• Versionamento• Cache ou buffer de escrita

• Conflitos• Protocolo de coerência de cache (snoop ou diretório)• R/W bits adicionados à cache

Page 125: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

125

HTM – Exemplo Execução

Versionamento e detecção de conflitos atrasados

Page 126: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

126

HTM – Exemplo Execução

Page 127: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

127

HTM – Exemplo Execução

Page 128: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

128

HTM – Exemplo Execução

Page 129: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

129

HTM – Exemplo Execução

Page 130: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

130

HTM – Herlihy & Moss (1993)

ISCA’93

Page 131: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

131

HTM – Herlihy & Moss (1993)

• Novas instruções (6)• ST, LT, LTX• COMMIT, VALIDATE, ABORT

• Cache transacional separada• Mantém os conjuntos de leitura e escrita da transação

• Protocolo de coerência• Baseado em snoop

Page 132: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

132

Problemas com a abordagem

• Cache adicional (em paralelo com as de dado e instruções) complica bastante o projeto de processadores modernos• Estender cache de dados tornou-se mais popular (1 bit extra para

read, e outro para escrita especulativa)

• Nenhuma virtualização• E se a cache transbordar?

• Uso ainda requer programador experiente

Page 133: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

133

Novos HTMs

• 2009 - Sun’s Rock

• 2009 – AMD Advanced Synchronization Facility (ASF)

• 2011 - IBM BlueGene/Q

• 2013 – Intel Transactional Synchronization Extensions (TSX) Processador acaba de ser lançado (Haswell)

Nosso foco

Page 134: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

134

IBM BlueGene/Q

• Revelado no Hot Chips 2011• 18 cores @1.6GHz• 16 cores para aplicações, 1

para SO, 1 aumentar yield

• Usados no supercomputador Sequoia

• Each core• 1.47 Billion transistors• 55 Watts

Page 135: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

135

Blue Gene/Q packaging hierarchy

5a. Midplane16 Node Cards

5b. I/O Drawer8 I/O Cards

8 PCIe Gen2 slots

3. Compute CardOne single chip module,16 GB DDR3 Memory2. Module

Single Chip

4. Node Card32 Compute Cards,

Optical Modules, Link Chips, Torus

6. Rack2 Midplanes

1, 2 or 4 I/O Drawers

7. System 20PF/s

1. Chip16 cores

Ref: SC2010 Slide produced by Martin Ohmacht for PACT 2011 Workshop

Page 136: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

Suporte Para Operacões Atômicas na L2

IEEE Micro, March/April 2012

Page 137: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

Example

Thread0

Thread1

Thread63

Page 138: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

138

L2 structure

Crossbar switch

DEVBUS

L2_central

L2_counter

L2

memorycontroller

L2L2L2L2L2L2L2

L2_counterL2_counter

L2L2L2L2L2L2L2L2

L2_counter

memorycontroller

• 32 MB / 16 way set-associative / 128B por linha / 256K linhas na cache• Ponto de coerência• Cada fatia:

• 2MB / 16K lines 1024 sets com 16 linhas/set⇒• 1024 sets

Slide adapted from Martin Ohmacht’s presentation at Workshop held at PACT 2011

Page 139: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

Uma visão simplificada da organização lógica de um slice da L2 (32MB)

Tag128BData

ThreadID

SpeculativeBit

11…11

16K

16 ways

00…00Index

16K linhas x 16 ways x 128 Bytes = 32M Bytes

Page 140: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

Diretório da L2

Para cada linha escrita especulativamente, o diretório armazena um id da thread que é a dona.

Quando ocorre um acesso a uma linha especulativa, o diretório compara a id da tread fazendo o acesso com a id da dona, e interrompe o thread mais jovem que está em conflicto.

Se o conflito é entre uma thread especulativa e um thread não especulativa, a thread especulativa é abortada.

Page 141: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

Speedup com relação à execução sequential

Page 142: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)
Page 143: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

143

• Memória Transacional veio para ficar como um novo paradigma de programação paralela

• Duas grandes empresas na área lançaram processadores contendo extensões para TMs (IBM e Intel)

• Boas oportunidades para realização de pesquisa!

• Se estiver interessado em fazer pesquisa entre em contato!!

Conclusões

Page 144: Guido  Araujo  (IC-UNICAMP) email:  guido@ic.unicamp.br Alexandro Baldassin  (IGCE-UNESP)

OBRIGADO!


Recommended