Orientador: Arthur J. Catto

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

Resumo: Na busca de propostas mais eficientes para se alcançar altos níveis de paralelismo, o Modelo de Fluxo de Dados (MFD) emergiu como um caminho novo e promissor a ser seguido. O MFD advoga uma representação clara e uma manipulação fácil do paralelismo dos programas. Dentre as pesquisas que...

Resumo: Na busca de propostas mais eficientes para se alcançar altos níveis de paralelismo, o Modelo de Fluxo de Dados (MFD) emergiu como um caminho novo e promissor a ser seguido. O MFD advoga uma representação clara e uma manipulação fácil do paralelismo dos programas. Dentre as pesquisas que abordam computação por fluxo de dados, a Máquina de Fluxo de Dados de Manchester (MFDM) ocupa uma posição importante, uma vez que ela foi uma das primeiras máquinas de fluxo de dados a serem projetadas e construídas. O Projeto de Fluxo de Dados de Manchester aventurou-se por um novo caminho e, durante mais de uma década, atingiu muitos dos seus objetivos. Dentre esses, destacam-se análises pioneiras de um sistema baseado no MFD. Nessas análises, duas medidas, Pby e PM, foram largamente utilizadas como indicadores consistentes do comportamento da Unidade de Emparelhamento (UE) e do desempenho das execuções no sistema, respectivamente, apesar de elas serem medidas "brutas". Embora não se negue aqui a importância dessas duas medidas, mostra-se que falhas na sua aferição podem ter causado deturpado análises anteriores. Nesta dissertação, demonstra-se que as medidas Pby e PM não são indicadores tão consistentes como se admitia. Infelizmente, não se propõe qualquer medida al. ternativa. Entretanto, pode-se concluir que a análise do comportamento e do desempenho da MFDM deveria ser conduzi da com parâmetros mais dinâmicos. Nos primeiros estágios do projeto da MFDM, observou-se uma perda de desempenho sensível. Desde então, no intuito de corrigir problemas iniciais, vários estudos foram realizados. Esta dissertação aborda especialmente o desempenho do escalonamento de instruções na MFDM. A técnica de escalonamento da MFDM usa a política "primeiro a chegar, primeiro a sair" (FIFO), que ordena os dados com base na ordem de chegada dos pacotes. Demonstra-se aqui que a técnica FIFO satura a Unidade de Emparelhamento (UE) produzindo seqüências indesejáveis de pacotes, as quais reduzem o throughput da UE e, conseqüentemente, o desempenho do sistema. A UE é apontada nas publicações afins como o "gargalo" do sistema. Aqui se apresenta uma análise dos efeitos da substituição da técnica de escalonamento FIFO por técnicas mais elaboradas. Um simulador da MFDM, gMDMS, foi implementado durante este estudo com o objetivo de comparar o desempenho da técnica FIFO com outras técnicas de escalonamento conhecidas, como HLFNET e CP jMISF. Os resultados obtidos utilizando-se gMDMS permitem concluir que a adoção da técnica FIFO é uma causa indireta da perda real de desempenho apresentada pela MFDM. Por isso, a especialização do controle da ordem do fluxo dos dados pelo anel provoca. uma grande melhora da utilização das unidades da máquina e o conseqüente aumento do desempenho do sistema

Abstract: In the research for more efficient approaches to reach very high levels of parallelism, DFM (Dataflow Model) emerged as a new and thriving way to follow. DFM advocates a very clear e presentation and easy manipulation of program parallelism. Among the researches on dataflow computation,...

Abstract: In the research for more efficient approaches to reach very high levels of parallelism, DFM (Dataflow Model) emerged as a new and thriving way to follow. DFM advocates a very clear e presentation and easy manipulation of program parallelism. Among the researches on dataflow computation, the MDFM (Manchester Dataflow Machine) takes an important place, because it is one of the first dataflow machines designed and built. Manchester Dataflow Project did venture a new pathway, and did achieve many of its expected goals over more than a decade. One of the greatest contributions of this machine project is the set of pioneering analyses of a dataflow system. In these analyses two measures, Pby and AP, were widely used as consistent indicators of the Matching U nit behavior and the system execution performance, respectively, despite their crude nature. We do not deny the importance of those two measures, but we show here that a deficiency in checking up on the effectiveness of them may have caused some misunderstandings in the previous analyses. In this thesis we show that those two measures, Pby and AP, are not so consistent indicators as they were stated to be. Unfortunately, we could not propose any sound alternative measures. But we can conclude that the analysis of the behavior or performance of MDFM should take place more dynamically. At the first stages of project, it was pointed out that the MDFM showed a lack of performance. Since then, to overcome the initial problems, several studies have been conducted. This thesis specially subjects the instruction scheduling performed in the MDFM. The MDFM scheduling technique uses the first-in-first-out (FIFO) policy. The FIFO technique orders the entries based on the packet arriving order. We believe this technique overloads the Matching Unit (MU) by producing undesirable token packet sequences, which decrease the MU throughput and, consequently, the system performance. The MU is pointed out as the bottleneck of the system in the related publications. An analysis of the effects of changing FIFO scheduling technique to a more elaborate one is here performed. For the purpose of comparison, some well-known scheduling techniques, such as HLFNET and CP jMISF, are simulated in the MDFM simulator gMDMS. We conclude that FIFO technique is an indirect cause of the actual loss of performance seen in the MDFM. Therefare, specializing the controlling of the data flow order in the system ring provides a great improvement in the unit utilization, and consequently an impravement