Qual é o modelo teórico certo para projetar algoritmos para computadores de alto desempenho atuais e futuros

20

Essa pergunta é semelhante a uma pergunta mais geral sobre qual é o modelo teórico correto de um computador para projetar estruturas de algoritmos e dados.
Aqui, pergunto especificamente sobre os atuais computadores de alto desempenho (como os listados como os 500 principais ) ou mesmo sobre próximos supercomputadores.

Dado que esses computadores normalmente estão trabalhando em grandes conjuntos de dados (parece que algumas pessoas usam essas máquinas principalmente porque possuem uma memória principal combinada enorme) aspectos do modelo de E / S (introduzido por Aggarwal e Vitter em 1988 ) e sua versão paralela , o PEM ( Arge, Goodrich, Nelson e Sitchinava em 2008 ) deve estar presente. Por outro lado, deve haver algo sobre comunicação, em particular punir pacotes ultra pequenos para todos os outros nós de computação.

Como você pode imaginar, não tenho medo de ficar sem ideias ao criar um novo modelo, mas estou um pouco preocupado que possa ignorar as tentativas anteriores, principalmente porque tenho a impressão de que os anos 1980- Em 1995, mais ou menos, muitas dessas tentativas de modelagem (como BSP ou modelos de ponte) que parecem não ter sido amplamente usadas.

Quais modelos devo examinar mais de perto?

reference-request soft-question machine-models Riko Jacob
fonte
isso não responde, mas qualquer modelo para supercomputadores atuais e futuros, mas incorpora falhas / tolerância a falhas.
Sylvain Peyronnet
Veja a taxonomia de Flynn. Segundo a Wikipedia, "Todos os 10 principais e a maioria dos supercomputadores TOP500 são baseados em uma arquitetura MIMD". en.wikipedia.org/wiki/MIMD
Mohammad Al-Turkistany
você pode esclarecer a frase: "Por outro lado, deve haver algo sobre comunicação, em particular punir pacotes ultra pequenos para todos os outros nós de computação". isso é um erro de digitação? deveria estar empurrando ? Alguém poderia responder a essa pergunta com padrões de design paralelos, por exemplo, mapreduce, o CSP de Hoare? veja também cache de algoritmos alheios, wikipedia
vzn

Respostas:

9

No PODC 2009, Bruce Hendrickson fez uma palestra convidativa fenomenal sobre essas questões. (Os slides dele não parecem estar online, mas você pode perguntar se pode vê-los.) Acho que ainda não há um modelo "certo" - bônus para você! - mas eu sugiro que você analise os documentos dele, especialmente os da página Gráficos e arquiteturas , onde ele tenta descobrir como lidar com gráficos enormes com pouca estrutura (isto é, conjuntos de dados "modernos") em máquinas multithread maciças.

Aaron Sterling
fonte
Obrigado pelo ponteiro. Olhando através dela, tenho a impressão de que ele não está muito interessado em definir um modelo que permita a análise teórica. Eu negligencio alguma coisa? Talvez eu deva contatá-lo diretamente.
Riko Jacob
@Riko Jacob: Eu concordo que Hendrickson é mais um praticante do que um modelador. Eu pensei que ele tinha uma excelente intuição para o que era necessário, no entanto. Se você deseja documentos sobre modelos, pode estar mais interessado no Workshop de Teoria e Muitos Núcleos . Não acho nenhum desses modelos satisfatório e ficaria muito interessado em ver o que você cria. :-)
Aaron Sterling
8

Uma questão que não está clara é como os caches serão desenvolvidos. O ano de 2009 tese de de Nikos Hardavellas considera essas coisas da perspectiva de sistemas, incluindo considerações de limites físicos para sistemas de memória escalável. A tese não apresenta um modelo como tal, mas pode fornecer algumas pistas.

Rasmus Pagh
fonte
4

⌈registro⁡x⌉

Suresh Venkat
fonte
Depois de olhá-lo, parece-me um antecessor do modelo que não presta atenção ao cache. Também não vi nenhuma idéia sobre processamento paralelo. Perdi alguma coisa aqui?
Riko Jacob 15/02
Eu acho que é mais sobre modelos de memória hierárquica, isso é verdade.
Suresh Venkat