Author: ziyang.eecs.umich.edu
TGFF
Versão do Windows de TGFF 3.1 (apenas binário)
Design original: David Rhodes e Robert Dick.
Desenvolvimento subseqüente: Keith Vallerio.
Task Graphs For Free (TGFF) foi projetado para fornecer uma maneira flexível e padrão de gerar gráficos de tarefas pseudo-aleatórias para uso na pesquisa de agendamento e alocação. Isso inclui as áreas de sistemas embutidos, co-design de hardware / software, sistemas operacionais (em tempo real e de propósito geral), estudos de hardware ou software paralelos ou distribuídos, agendamento de fluxo de loja, bem como qualquer outra área que exija problema instâncias que consistem em gráficos acíclicos (DAGs) parcialmente encomendados ou dirigidos de tarefas, como o, task-graphs.
Enquanto o TGFF se esforça para ser de propósito geral, ele gera gráficos e parâmetros de recursos associados de acordo com o gráfico parametrizado do usuário e as especificações do banco de dados e, assim, permite a geração de gráficos adaptados a domínios específicos.
O task-graphs (DAGs) gerado pelo TGFF pode ser facilmente restrito a out-trees via parâmetros do usuário. Por exemplo, uma árvore externa aleatória pode ser gerada limitando o parâmetro em grau a 1. Gráficos série paralelos, gráficos que consistem em múltiplas cadeias de nós vinculados sequencialmente, podem ser gerados usando o novo algoritmo. Os gráficos resultantes podem ser vistos como um arquivo postscript ou usando VCG. (Um exemplo comparando as versões eps e vcg da saída TGFF pode ser encontrado aqui.)
Podem ser gerados casos periódicos ou aperiódicos. Para casos periódicos, o usuário especifica um conjunto de inteiro multiplicadores-de-período que determinam os períodos relativos dos múltiplos gráficos de tarefas em cada caso. Por exemplo, as abordagens de soluções múltiplas (LCM) menos comuns podem ser dificultadas pela escolha de números relativamente primos. Um fator de laxação do período é usado para determinar a laxitud relativa do período do gráfico da tarefa em relação aos prazos de suas tarefas.
Os prazos para cada tarefa sem filhos em todos os gráficos de tarefas são determinados com base no nível da tarefa e um fator de laxação de prazo. Os casos desafiadores podem ser gerados, tornando o laxismo pequeno, enquanto que instâncias relativamente mais fáceis podem ser criadas tornando-o grande. Para conjuntos de tarefas produzidos com as configurações padrão do TGFF, não há garantia de viabilidade para os horários produzidos. Para outra abordagem de definição de prazo, veja a ferramenta packed schedules . (Por favor, note que os horários embalados não podem ser usados com alguns dos novos recursos. Notavelmente, a saída do VCG e as opções do task graph série-paralela não estão disponíveis para packed schedules.)
Os atributos de processador, comunicação e tarefa podem ser declarados e relacionados de forma correlacionada, juntamente com um atributo de tamanho-de-dados de comunicação entre tarefas.
O programa e seu gerador de números pseudo-aleatórios internos estão escritos em C ++ e são portáteis para arquiteturas com números de ponto flutuante de 32 bits que possuem mantisas de 24 bits. Isso permite que os pesquisadores gerem gráficos de tarefa idênticos, com parâmetros idênticos e sementes de entrada, permitindo a comparação direta de seus agendadores / alocadores. O programa fornece a saída principal em um arquivo de texto e também gera um arquivo PostScript encapsulado que representa os gráficos. Um exemplo da saída PostScript é mostrado no topo desta página.
Downloads
| Download o código fonte | Download papel (apenas algoritmo antigo) | Download documentação (pdf) |
Outros links
| Sugestões de extensão | Cronogramas embalados | Notas de versão |