learning plus: ILP Scheduling with DVFS constrain @ perl

在之前的 post 中 Force-Directed Scheduling with golden check @ perl 完成了 Syntax2SystemC gen 的部份, 雖然考慮到 cell 的 time delay 對 total avg power 的 optimal. 但這也只是 static power saving 的動作. 但其實在 timing path 上, 可以針對每個 processor element 加入不同的 frequency or power supply 來 inc/dec timing path 上的 delay, 讓 design 能夠更 meet 我們所需要的 constrains learning plus: DVFS emulator SmartReflex™ Power and Performance Management Technologies 底下就針對 DVFS 如何加入到 DFG graph 中的方式做探討. flow chart

step1. 產生 DFG graph. step2. 產生 constrain DFG graph @ time/hardware constrains step3. find time critical path. 針對 critical path 上的 vertex 插入 DVFS vertex. 來 balance critical path. 且再最後 arch gen 的時候, 能夠 cluster 在同個 PE 底下. step3. 用 ILP + 標準差的方式找出在 constrain 下的最佳 min sum(peak power) 的解. step4. explore SystemC

ILP flow
1. Nv is the total number of vertex operations in the sequencing DFG, excluding the
source and sink nodes (NO–OPs).
2. vi is any vertex in the DFG performing certain operations and 1 ≤ i ≤ Nv .
3. FUk is the functional unit of type k.
4. Mk is the maximum number of functional units of type FUk .
5. Costk is cost of functional unit of type FUk may be power, area or delay.
6. CS [i] is the ASAP time stamp for the operation vi .
7. CL [i] is the ALAP time stamp for the operation vi .
8. xi,c is the binary decision variable which is 1 if vertex vi starts in control step c,
else 0.

sample code case for 5 taps fir

#!/usr/bin/perl


use Data::Dumper;
use SysPerl::syntax2DFG;
use SysPerl::constrain2DFG;
use SysPerl::schedule::integer_linear_programming;
#use SysPerl::schedule::force_directed;
use SysPerl::arch::arch2DFG;
use strict;

#===================================
# @step 1 : gen simple DFG graph
# return  : DFG graph
#         : vertex_pre_stack 
#         : vertex_nxt_stack
#===================================
# 
#  y = b0*x0 + b1*x1 + b2*x2 + b3*x3 + b4*x4 + b5*x5;

my $tt = ['y','=','b0','*','x0','+',
                 ,'b1','*','x1','+',
                 ,'b2','*','x2','+',
                 ,'b3','*','x3','+',
                 ,'b4','*','x4','+',
                 ,'b5','*','x5',';'];

my $syn  = SysPerl::syntax2DFG->new();
   $syn->read_text($tt);
   $syn->run_text();
   $syn->free();

#   my $graph = $syn->get_deep_copy_graph();  
 
# remove tmp_reg && feedback assign 
# ex : d=c;
#      e=d+1;
    $syn->run_updt_DFG();

# get all graph && DFG flow 2 schedule 
my $DFG = $syn->get_deep_copy_DFG();

# dump graph as dot file    
  $syn->dump_DFG_graphviz_file('syn2DFG.dot');
  $syn->free();

#=====================================
# @step2. : 
# flow 1  : insert time weighted constrain 2 simple DFG graph and
#           gen Cstep graph(cycle step grpah)
# flow 2  : insert average power weighted constrain 2 Cstep and gen the force vale 
#           @ force directed scheduling
# return :  cycle graph
#=====================================
# set unit time wait delay
my $constrain_time_weighted_vertices = { 
     '+'  => 1,   # add delay 1 unit s
     '-'  => 1,   # sub delay 1 unit s
     '*'  => 1,   # mul
     '/'  => 1,   # div
     '%'  => 1,   # rem
     '>>' => 1,   # rsht
     '<<' => 1,   # lsht
};

#set unit average power consumed
my $constrain_power_weighted_vertices = {
     '+'  => 1.54,
     '-'  => 1,
     '*'  => 6.7,
     '/'  => 1,
     '%'  => 1,
     '>>' => 1,
     '<<' => 1,
};

my $con = SysPerl::constrain2DFG->new();
   $con->set_deep_DFG($DFG);

   $con->set_constrain_time_weighted($constrain_time_weighted_vertices);
   $con->set_constrain_power_weighted($constrain_power_weighted_vertices);

   $con->run_constrain_time_weighted_DFG();
   $con->run_constrain_NewDFG();
 
#   $con->dump_ALUDFG_graphviz_file('alu.dot');
   $con->dump_NewDFG_graphviz_file('con.dot');

#=============================
# schedule && cluster
#=============================
#my $sch = SysPerl::schedule::force_directed->new();
#   $sch->set_deep_cons2DFG($con);
#
#   $sch->run_forece_directed_scheduling();
#   $sch->report();

my $pe_number_constrain = {
     '+'  => 2,   # add numbers constrain for each time step
     '-'  => 2,   # sub 
     '*'  => 2,   # mul
     '/'  => 2,   # div
     '%'  => 2,   # rem
     '>>' => 2,   # rsht
     '<<' => 2,   # lsht
};

my $sch = SysPerl::schedule::integer_linear_programming->new();
   $sch->set_deep_cons2DFG($con);

   $sch->set_pe_number_constrain($pe_number_constrain);
   $sch->run_integer_linear_programming_scheduling();
   $sch->report();

#=============================
# explore hardware
#=============================  
my $arc = SysPerl::arch::arch2DFG->new();
   $arc->set_deep_sched2arch($sch);
   $arc->run_ALU_cluster();
   $arc->run_explore_SystemC();

project: https://github.com/funningboy/hg_lvl_syn/blob/master/main_ILP.pl Ref : 以多重電位操作之VLIW架構下運用ILP為基礎之低功率排程演算法