1 Workshop GrecO 2005 Remy Eskinazi ([email protected]) “Uma Metodologia Baseada em Redes de Petri Temporizadas para a geração de Escalonamento Estático

1

WorkshopGrecO 2005Remy Eskinazi ([email protected])

“Uma Metodologia Baseada em Redes de Petri Temporizadas para a geração de Escalonamento Estático em Arquiteturas Dinamicamente Reconfiguráveis”

2

Informações Gerais

• Equipe– Aluno: Remy Eskinazi– Orientador: Prof. Manoel Eusebio– Linha de Pesquisa: Sistemas Reconfiguráveis– Curso: Doutorado em Ciências da Computação– Equipe:

• Paulo Sergio (Aluno PhD)• Jordana Seixas (Aluna MSc)• Halmos Nascimento (Aluno MSc)• Stelita Silva (Aluna IC)• Pablo Santana (Aluno colaborador)

3

Mercado de Sistemas Embarcados

• Desafios para Sistemas Embarcados (M. Barr – Netrino Consultants)

– Fazer mais (Melhor desempenho);

– Custar menos ($/unidade, lote);

– Ser trazido ao mercado mais rapidamente (TTM);

• Praticamente impossível de alcançar estas metas ao mesmo tempo com o uso de métodos de projeto tradicionais (ASICS)

4

Paradigma da computação reconfigurável

Microprocessador

• Uso geral

• Desempenho relativo (media das aplicações)

ASIC

•Uso específico

•Excelente desempenho

Aumento da Flexibilidade

Aumento da Performance

FPGAs

•Flexibilidade

•Desempenho

Custo/unidade

5

Descrição do Problema

• Sistemas embarcados reconfiguráveis pressupõe a troca de contextos ou tarefas de hardware

– IP cores (Núcleos de hardware de finalidade específica)

• Sistemas reconfiguráveis que apresentam tarefas com forte restrição temporal

– Sistemas reconfiguráveis em tempo real– Métodos de escalonamento que atendam as

restrições temporais

6


• Exemplo:– Tarefas em tempo real especificadas em termos de

tempo de liberação, tempo de computação, e tempo máximo para computação ( Task = (Rt, Ct, Dt))

– Tarefas:• A=(0, 6, 10)• B=(2, 2, 4)• C=(0, 18, 20)

7


Tarefas:• A=(0, 6, 10)• B=(2, 2, 4)• C=(0, 18, 20)

C A/B

I

II

I II

18C

6 8A B

I

II18

C

102AB

Scheduling Estático

Scheduling Dinâmico

FPGA

4

8

Motivação

• Utilização de SDRs apresenta-se como uma forte tendência para implementação de Sistemas embarcados;– Densidade funcional em áreas reconfiguráveis– Armazenamento externo de tarefas não ativas

• Custos decrescentes associado com maior densidade de lógica dos FPGAs;– Xilinx Spartan XL 5 Kgates => US$ 2,49

• Utilização de Biblioteca de núcleos de hardware (HW cores) customizados a arquitetura– Reuso com funcionalidade assegurada– Eficiência devido a combinação com a arquitetura

9

Motivação

• Implementação de sistemas computacionais complexos– Controladores RISC de alta eficiência

• MicroBlaze, PPC, NiOS, ARM ...• Memórias, controladores de barramento

• Carência de metodologias para implementação de SDRs– Ferramentas de implementação próximas ao nível

de síntese física– Heterogeneidade das aplicações dificulta a

implementação– Carência de metodologias de gerenciamento de

troca de contextos (tarefas em hardware)

10

Objetivos

• Desenvolvimento de uma metodologia para geração de escalonamento estático para sistemas dinamicamente reconfiguráveis (SDRs)– Otimização temporal de execução de tarefas de

hardware em tempo real– Representação interna em TPN

• Desenvolvimento de um framework para desenvolvimento de SDRs– Ferramenta para geração dos modelos das tarefas

em TPN

• Desenvolvimento de uma arquitetura padrão reconfigurável– Conceito de “virtual hardware socket”

11

Resolução do problema

1. Mapeamento das características da aplicação em uma TPN (Timed Petri Net);• Número de áreas reconfiguráveis

• Características individuais das tarefas

– Ti = {Ri, Ci, Di}

• Precedência

• Deadline da aplicação

12

Resolução do problema

2. Análise estrutural da RdP gerada de forma a se obter:• Alcançabilidade de marcação final;

• Grafo de estados para uma determinada marcação

• Determinar a seqüência de disparos de transições para obter o menor tempo decorrido para a marcação desejada

13

Resolução do problema – Modelos em TPN

• Modelo de tarefa

• Modelo de precedência

• Modelo da aplicação

14

Fluxo de projeto

M o d u l a r D e s i g n

T a s k s S y n t h e s i s

E m b e d d e d C o n t r o l S y s t e m

C o n f i g u r a t i o n G e n e r a t i o n

V i r t e x I I ( T a r g e t )

D o w n l o a d

L E A






D o w n l o a d

L E A

T P N A p p l i c a t i o n

M o d e l


M o d e l


M o d e l


M o d e l

S c h e d u l i n g A n a l y s e s




T P N A n a l y z e r ( t e m p o r a l

p e r f o r m i n g )







P r e R u n t i m e s c h e d u l i n g G e n e r a t i o n




A p p l i c a t i o n R e q u i r e m e n t s

T a s k s D e s c r i p t i o n

( V H D L )


( V H D L )


( V H D L )


( V H D L )

S y n t h e s i s

T i

t iN

. . .

T s

t s

T j

t j

. . .

E n d P r o c e s s

S t a r tT a s k T i

T a s k

T s

T a s k T j

P a

. . .

A r b i t e r

A p p l ic a t i o n D e a d l in e

T D j

D t j

T D j

D t j

. . .

T D i

D t i

0001t 1

0110

001

t 2 t 3

1100t 1

010

001

t 2 t 3

100 t e r m i n a l

d u p l ic a d ot e r m in a l

E s t i m a t i v a sá r e a e t e m p o

A

B

CD

E

F

G

A 1 A 2 A 3

T 1

T 2

T 3

T 4

T 5

T 6

D

G

C

AF

B

E

Aplicação

Foco da Tese

15

Fluxo de projeto






D o w n l o a d

L E A






D o w n l o a d

L E A


M o d e l


M o d e l


M o d e l


M o d e l

















A p p l i c a t i o n R e q u i r e m e n t s


( V H D L )


( V H D L )


( V H D L )


( V H D L )

S y n t h e s i s

T i

t iN

. . .

T s

t s

T j

t j

. . .

E n d P r o c e s s

S t a r tT a s k T i

T a s k

T s

T a s k T j

P a

. . .

A r b i t e r

A p p l ic a t i o n D e a d l in e

T D j

D t j

T D j

D t j

. . .

T D i

D t i

0001t 1

0110

001

t 2 t 3

1100t 1

010

001

t 2 t 3

100 t e r m i n a l

d u p l ic a d ot e r m in a l

E s t i m a t i v a sá r e a e t e m p o

A

B

CD

E

F

G

A 1 A 2 A 3

T 1

T 2

T 3

T 4

T 5

T 6

D

G

C

AF

B

E

Aplicação

Modelo Tarefas

SystemC

Modelo Escalonador

Modelo Arquitetura

Resultados da

validação

Foco da Tese

16

Resultados obtidos

• Viabilidade do modelo– Garantia de um número de estados possível de

análise

• Modelamento de aplicação com tarefas de Hardware– Geração de escalonamento de tarefas

• Geração de modelos de tarefas em SystemC– (Em andamento)

17

PublicaçõesRemy Eskinazi, Paulo Maciel, Manoel Eusebio, Paulo Nascimento, Abel Guilhermino, Carlos

Valderrama, “A Timed Petri Net Approach for Pre-Run time Scheduling in Partial and Dynamic Reconfigurable Systems”, The 12th Reconfigurable Architectures Workshop (RAW 2005), Denver Colorado, USA, April 2005. ISBN 0-7695-2312-9

Remy Eskinazi, Paulo Maciel, Manoel Eusebio de Lima, Paulo Sergio Nascimento, Abel Guilhermino,

Carlos Valderrama, “A Methodology for Hardware Tasks Scheduling Optimized in Time for Partial and Dynamic Reconfiguration of FPGAs”, International Workshop on Applied Reconfigurable Computing (ARC 2005) - Algarve, Portugal, February 22-23, 2005. ISBN: 972-99353-6-X

Remy Eskinazi, Manoel E. de Lima, Paulo R. M. Maciel, Carlos A. Valderrama, Abel G. Filho, Paulo S.

B. Nascimento, “A Petri-Net Based Pre-Runtime Scheduler for Dynamically Self-Reconfiguration of FPGAs”, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, Pages: 262 – 262, Monterey, California, USA February 20 - 22, 2005 ISBN: 1-59593-029-9

Remy Eskinazi, Manoel Eusebio de Lima, Paulo Romero Martins Maciel: A Left-Edge Algorithm

Approach for Scheduling and Allocation of Hardware Contexts in Dynamically Reconfigurable Architectures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field-programmable gate arrays, Pages 259 – 259, Monterey, California, USA February 22 - 24, 2004. ISBN:1-58113-829-6

Paulo Sérgio B. Nascimento, Paulo Romero M. Maciel, Manoel E. Lima, Remy Eskinazi, Abel

Guilhermino S. Filho, “A Partial Reconfigurable FPGA Implementation for Industrial Controllers Using SFC-Petri Net Description”, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, Pages: 262 – 262, Monterey, California, USA February 20 - 22, 2005. ISBN:1-59593-029-9

18

Publicações

Paulo Sérgio B. Nascimento, P. R. M. Maciel, M. E. Lima, Remy. Eskinazi, e A.G. da Silva Filho, “A Partial Reconfigurable Architecture for Controllers Based on Petri Nets”, Proceedings of the 17th Symposium on Integrated Circuits and Systems Design (SBCCI) Pernambuco, Brazil September 7-11, 2004). ISBN 1-58113-947-0

Remy Eskinazi; Manoel Eusebio de Lima.; MACIEL, P. R.. Introdução ao Estudo de

Hardware/Software Co-design com Aplicação em Arquiteturas Dinamicamente Reconfiguráveis, Guarujá. Proceedings - WCETE 2004 - World Conference on Engineering and Technology Education, 2003 ISBN 85-89120-12-0

Remy Eskinazi.; Manoel Eusebio de Lima.; MACIEL, P. R.. A Reconfigurable Architecture

for Multi-Context Application. In: International Conference on Engineering and Computer Education - ICECE 2003, Santos/São Vicente. Proceedings - International Conference on Engineering and Computer Education - ICECE 2003. ISBN 85-89120-08-2

Remy Eskinazi.; Manoel Eusebio de Lima.; MACIEL, P. R.. Uma Metodologia de

Reconfigurabilidade Baseada na Plataforma de Prototipação Chameleon. In: Simpósio de Computação reconfigurável, 2001, Minas Gerais. SCR-2001 - PUC-MG, 2001.

19

Conclusões

• Uma Metodologia para escalonamento estático em arquitetura dinamicamente reconfigurável é proposta;

• A Metodologia apresenta como principal característica a otimização temporal da execução das tarefas de hardware em tempo real;

• A implementação experimental esta correntemente sendo feita em arquitetura Virtex II– Atualmente na fase validação em SystemC

• Desenvolvimento de um Framework de apoio ao projeto

20

Conclusões

• Trabalhos futuros – Considera-se um modelo em TPN de forma a

otimizar a área estimada das tarefas com as áreas na arquitetura destinadas a reconfiguração

• Diminuição do efeito de fragmentação interna

• Diminuição da sobrecarga de reconfiguração

– Implementação do modelo do escaonador em uma arquitetura composta por 2 FPGAs

• Módulo de controle e de configuração

Documents

1 Workshop GrecO 2005 Remy Eskinazi ([email protected]) “Uma Metodologia Baseada em Redes de Petri Temporizadas para a geração de Escalonamento Estático