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

  • View
    27

  • Download
    0

Embed Size (px)

DESCRIPTION

Programação Paralela usando Memórias Transacionais : da Academia à Indústria. IV Escola Regional de Alto Desempenho de São Paulo j ulho de 2013. Guido Araujo (IC-UNICAMP) email: guido@ic.unicamp.br Alexandro Baldassin (IGCE-UNESP) e mail: alex@rc.unesp.br. Blue Gene/Q. Roteiro. - PowerPoint PPT Presentation

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

Slide 1

Guido Araujo (IC-UNICAMP)email: guido@ic.unicamp.br

Alexandro Baldassin (IGCE-UNESP) email: alex@rc.unesp.br

Blue Gene/QProgramao Paralela usando Memrias Transacionais: da Academia IndstriaIV Escola Regional de Alto Desempenho de So Paulojulho de 20131RoteiroParte 1 Programao paralela na atualidadeTransaes: uma estratgia otimistaModelo de execuo

Parte 2Arquitetura bsica de uma STMExemplo usando o GCCArquitetura bsica de uma HTMIBM BlueGene Q

2Parte 1Introduo e Conceitos BsicosSistema de memria compartilhada

c0c1c2c3countertempstore (counter, temp)tempload (temp, counter)Usado como modelo de execuo de Pthreads e OpenMPMemria CompatilhadaProcesso cria vrias threads de execuoThreads compartilham espao de endereamentoComunicao feita diretamente atravs de leituras e escritas em memria compartilhada Acessos concorrentes de leitura e escrita podem causar inconsistncias (condies de corrida)Sincronizao usada para evitar tais cenrios

5SincronizaoEvitar intercalaes inconsistentes de execuo6shared counter;void work(){ counter++;}Qual o resultado esperado aps a primeira execuo?shared counter;void work(){ counter++;}1a coisa: sentena na linguagem de programao != instrues que o processador executa6SincronizaoEvitar intercalaes inconsistentes de execuo7shared counter;void work(){ counter++;}i1: temp = load(counter);i2: temp = temp + 1;i3: store(counter, temp);Condio de corrida na varivel counter7SincronizaoEvitar intercalaes inconsistentes de execuo8i1: 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++)Exemplo de execuo com duas threads resultado esperado para counter == 28SincronizaoEvitar intercalaes inconsistentes de execuo9i1: 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++)

9SincronizaoEvitar intercalaes inconsistentes de execuo10i1: 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?10SincronizaoEvitar intercalaes inconsistentes de execuo11i1: 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?11SincronizaoEvitar intercalaes inconsistentes de execuo12i1: 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++)

12SincronizaoEvitar intercalaes inconsistentes de execuo13i1: 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++)

13SincronizaoEvitar intercalaes inconsistentes de execuo14i1: 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++)

14SincronizaoEvitar intercalaes inconsistentes de execuo15i1: 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?Resultado final deveria ser 2, mas acabou sendo 1.15Mecanismos de SincronizaoBloqueantestravas (locks)variveis de condio (condition variables)semforos/monitores

No-bloqueanteslivre de espera (wait-free)livre de trava (lock-free)livre de obstruo (obstruction-free)

16Nao entrar em detalhes sobre garantias de progresso nas no-bloqueantes. Terminar dizendo que os mecanismos sero vistos com mais detalhes no que se segue.16ExemploConsidere o seguinte problema: implementar uma lista de inteiros ordenados em ordem crescente, admitindo operaes como insero, remoo e consulta

Esta tarefa pode ser desenvolvida facilmente por alunos de disciplinas de introduo computao

Desejamos uma verso paralela, que permita operaes concorrentes na lista.

17Lista ordenada sequencial18class 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); }}Implementao da lista de inteiros ordenada como uma lista ligada.Ns sentinelas facilitar a programao18Lista ordenada sequencial19public 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;}acheadtailFuno retorna se conseguiu inserir item ou no (item repetido ou no)Lista contm os items a e c - Inserir nodo bImportante entender essa verso para ver como paralelizar depois19Lista ordenada sequencial20public 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;}acheadtailpredcurradd(b)Fico varrendo a lista at achar um elemento que seja maior ou igual ao curr.key -> nesse momento, pred aponta para item anterior

20Lista ordenada sequencial21public 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;}acheadtailpredcurradd(b)Por construo no pode haver nenhum item na lista maior do que o que est sendo inserido -> evita necessidade de checar por NULL21Lista ordenada sequencial22public 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;}acheadtailpredcurrbadd(b)22Lista ordenada sequencial23public 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;}acheadtailpredcurrbadd(b)23Lista ordenada sequencial24public 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;}acheadtailpredcurrbadd(b)24Lista ordenada sequencial25public 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;}acheadtailpredcurrbpublic 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;}abcheadtailpredcurrremove(b)Remover bMesma ideia que add, porm quando acho o item a ser removido, fao pred.next = curr.next25ParalelizandoComo desenvolver uma verso paralela do exemplo anterior?

Sendo otimistaOperaes de insero, remoo e busca podem potencialmente ser executadas em paralelo

26abcheadtaildfThread 1remove(d)Thread 2search(b)ParalelizandoComo desenvolver uma verso paralela do exemplo anterior?

Sendo otimistaOperaes de insero, remoo e busca podem potencialmente ser executadas em paralelo

Mais seguroSer pessimista e assumir que sempre haver conflitosLock global

27Lista ordenada lock global28public 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;}28Lista ordenada lock global29public 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;}Soluo simples e correta!!!Seo crtica em negrito29Lista ordenada lock globalIdeia do lock globalAntes de iniciar o trecho de cdigo que altera a lista, adquirir a trava (lock)Aps trecho de cdigo, liberar a trava (unlock)Funciona?

30Soluo simples, mas no escala!Operaes so serializadas

Enfatizar o fato que com o lock global as operaes sero serializadas (tradeoff entre corretude e desempenho) -> lei de Amdahl((Uma forma possvel de melhorar a soluo usar outra estrutura de dados