cost_model.c File Reference

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "boolean.h"
#include <stdbool.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "database.h"
#include "misc.h"
#include "text.h"
#include "text-util.h"
#include "ri-util.h"
#include "effects-util.h"
#include "accel-util.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "pipsdbm.h"
#include "resources.h"
#include "control.h"
#include "c_syntax.h"
#include "conversion.h"
#include "properties.h"
#include "transformations.h"
#include "effects-convex.h"
#include "complexity_ri.h"
#include "complexity.h"
#include <time.h>
#include "dg.h"
#include "graph.h"
#include "ricedg.h"
#include "chains.h"
#include "task_parallelization.h"

Include dependency graph for cost_model.c:

Go to the source code of this file.

Typedefs
typedef dg_arc_label	arc_label
	Instantiation of the dependence graph: More...
typedef dg_vertex_label	vertex_label

Functions
bool	costly_task (statement st)
	cost_model.c More...
double	polynomial_to_numerical (Ppolynome poly_amount)
double	size_of_regions (list l_data)
static list	used_data (statement(st))
static double	task_time (statement s)
double	edge_cost (statement s1, statement s2)
double	t_level (vertex v, graph dg, gen_array_t annotations)
	First parameter is the top level (earliest start time) for each node. More...
void	top_level (graph dg, gen_array_t annotations)
void	bottom_level (graph dg, gen_array_t annotations)
	Second parameter is the bottom level (latest start time) for each node. More...
void	priorities (gen_array_t annotations)
void	initialization (graph dg, gen_array_t annotations)
void	parse_instrumented_file (char *file_name, graph dg, gen_array_t annotations)

Typedef Documentation

arc_label

typedef dg_arc_label arc_label

Instantiation of the dependence graph:

Definition at line 44 of file cost_model.c.

vertex_label

typedef dg_vertex_label vertex_label

Definition at line 45 of file cost_model.c.

Function Documentation

bottom_level()

void bottom_level	(	graph	dg,
		gen_array_t	annotations
	)

Second parameter is the bottom level (latest start time) for each node.

Parameters

dg	g
annotations	nnotations

Definition at line 223 of file cost_model.c.

{
  double max, level;
  list vertices = (graph_vertices(dg));
  annotation *an, *anp;
  FOREACH(VERTEX, v, vertices) {
    max = 0;
    statement sv = vertex_to_statement(v);
    FOREACH(VERTEX, pre, (graph_vertices(dg))) {
      statement parent = vertex_to_statement(pre);
      anp = gen_array_item(annotations, (int)statement_ordering(parent));
      FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
        vertex s = successor_vertex(su);
        statement child = vertex_to_statement(s);
        if(statement_equal_p(child, sv) && gen_array_item(annotations, (int)statement_ordering(parent)) )
          {
            double edge_c = *(double *)(gen_array_item(anp->edge_cost,statement_ordering(sv)));
            level = anp->blevel + edge_c;
            if(level > max)
              max = level;
          }
      }
    }
    an = gen_array_item(annotations, statement_ordering(sv));
    an->blevel = an->task_time + max;
    gen_array_addto(annotations, (int)statement_ordering(sv), an);
  }
  return;
}

References annotations, annotation::blevel, dg, annotation::edge_cost, FOREACH, gen_array_addto(), gen_array_item(), graph_vertices, level, max, statement_equal_p(), statement_ordering, SUCCESSOR, successor_vertex, annotation::task_time, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by BDSC(), and DSC().

Here is the call graph for this function:

Here is the caller graph for this function:

costly_task()

bool costly_task

(

statement

st

)

cost_model.c

Parameters

st

t

Definition at line 52 of file cost_model.c.

                              {
  bool costly_p = false;
  instruction inst = statement_instruction(st);
  if (statement_contains_user_call_p(st))
    return true;
  else{
    switch(instruction_tag(inst)){
    case is_instruction_block:{
      MAPL( stmt_ptr,
            {
              statement local_stmt = STATEMENT(CAR(stmt_ptr ));
              costly_p = costly_p || costly_task(local_stmt);
            },
            instruction_block(inst));
      return costly_p;
      break;
    }
    case is_instruction_test :{
      test t = instruction_test(inst);
      return costly_task(test_true(t)) ||
        costly_task(test_false(t));
      break;
    }
    case is_instruction_loop :{
      return true;
    }
    case is_instruction_forloop :{
      return true;
    }
    case is_instruction_whileloop :{
      return true;
    }
    case is_instruction_call:{
      return user_call_p(statement_call(st));
    }
    default:
      return false;
    }
  }
}

References CAR, instruction_block, instruction_tag, instruction_test, is_instruction_block, is_instruction_call, is_instruction_forloop, is_instruction_loop, is_instruction_test, is_instruction_whileloop, MAPL, STATEMENT, statement_call(), statement_contains_user_call_p(), statement_instruction, test_false, test_true, and user_call_p().

Referenced by cluster_stage_spire(), cluster_stage_spire_generation(), hierarchical_schedule(), and hierarchical_schedule_step().

Here is the call graph for this function:

Here is the caller graph for this function:

edge_cost()

double edge_cost	(	statement	s1,
		statement	s2
	)

Parameters

s1	1
s2	2

Definition at line 147 of file cost_model.c.

{
  Ppolynome transfer_time = POLYNOME_NUL;
  list l_write = regions_dup(regions_write_regions(load_statement_local_regions(s1)));
  list l_read = regions_dup(regions_read_regions(load_statement_local_regions(s2)));  
  list l_communications = RegionsIntersection(regions_dup(l_write), regions_dup(l_read), w_r_combinable_p);
  FOREACH(REGION,reg,l_communications){
    Ppolynome reg_footprint = region_enumerate(reg); 
    //reg_footprint =  polynome_mult(reg_footprint, expression_to_polynome(int_to_expression(SizeOfElements(variable_basic(type_variable(entity_type(region_entity(reg))))))));
    //reg_footprint =
    //polynome_mult(reg_footprint,expression_to_polynome(int_to_expression(2.5)));//\beta= 2.5 on Cmmcluster
    polynome_add(&transfer_time, reg_footprint);
  }
  //polynome_add(&transfer_time, latency);// the latency \alpha = 15000 on Cmmcluster
  //polynome_fprint(stderr,transfer_time,entity_local_name,default_is_inferior_var);
  return polynomial_to_numerical(transfer_time);
}

References FOREACH, load_statement_local_regions(), polynome_add(), POLYNOME_NUL, polynomial_to_numerical(), REGION, region_enumerate(), regions_dup(), regions_read_regions(), regions_write_regions(), RegionsIntersection(), s1, and w_r_combinable_p().

Referenced by initialization().

Here is the call graph for this function:

Here is the caller graph for this function:

initialization()

void initialization	(	graph	dg,
		gen_array_t	annotations
	)

Parameters

dg	g
annotations	nnotations

Definition at line 267 of file cost_model.c.

{
  list vertices = graph_vertices(dg);
  int sigma =  get_int_property("BDSC_SENSITIVITY");
  float clock = 1, overhead = 0;
  srand(time(NULL));
  FOREACH(VERTEX, v, vertices){
    statement stmt = vertex_to_statement(v);
    annotation *item = (annotation *)malloc(sizeof(annotation));
    float x = (float)((float)rand()/((float)RAND_MAX) * (float)sigma/100);
    item->task_time = clock * task_time(stmt) * (1 + x ) + overhead;
    item->edge_cost = gen_array_make(gen_length(vertex_successors(v)));//0
    FOREACH(SUCCESSOR, su, (vertex_successors(v))){//statement_to_vertex(stmt, dg)))) {
      vertex s = successor_vertex(su);
      statement child = vertex_to_statement(s);
      double *ec = (double *)malloc(sizeof(double));
      *ec = clock * edge_cost(stmt, child) * (1+((float)rand()/(float)RAND_MAX * sigma/100)) + overhead;
      gen_array_addto(item->edge_cost, statement_ordering(child), ec);
    }
    item->scheduled = false;
    item->order_sched = -1;
    item->cluster = -1;
    item->nbclusters = 0;
    item->data =  used_data(stmt);
    gen_array_addto(annotations, (int)statement_ordering(stmt), item); 
  }
  return;
}

References annotations, annotation::cluster, annotation::data, dg, edge_cost(), annotation::edge_cost, FOREACH, gen_array_addto(), gen_array_make(), gen_length(), get_int_property(), graph_vertices, malloc(), annotation::nbclusters, annotation::order_sched, annotation::scheduled, statement_ordering, SUCCESSOR, successor_vertex, task_time(), annotation::task_time, used_data(), VERTEX, vertex_successors, vertex_to_statement(), and x.

Referenced by dsc_code_parallelization(), hbdsc_parallelization(), and make_unstructured_from_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

parse_instrumented_file()

void parse_instrumented_file	(	char *	file_name,
		graph	dg,
		gen_array_t	annotations
	)

Parameters

file_name	ile_name
dg	g
annotations	nnotations

Definition at line 296 of file cost_model.c.

{
  FILE *finstrumented;
  double cost;
  int ordering, ordering2;
  finstrumented = fopen(file_name,"r");
  list vertices = graph_vertices(dg);
  annotation *item;
  FOREACH(VERTEX, v, vertices){
    statement stmt = vertex_to_statement(v);
    item = (annotation *)malloc(sizeof(annotation));
    item->edge_cost = gen_array_make(0);
    FOREACH(SUCCESSOR, su, (vertex_successors(statement_to_vertex(stmt, dg)))) {
      vertex s = successor_vertex(su);
      statement child = vertex_to_statement(s);
      double *ec = (double *)malloc(sizeof(double));
      *ec = 0;
      gen_array_addto(item->edge_cost, statement_ordering(child), ec);
    }
    gen_array_addto(annotations, (int)statement_ordering(stmt), item);
  }
  while (!feof(finstrumented) && (fscanf(finstrumented,"%d->%d = %lf \n", &ordering,&ordering2, &cost)))
    {
      if(ordering2 == -1){
        item = gen_array_item(annotations, ordering);
        item->task_time = (double)cost;
        if(item->edge_cost == NULL)
          item->edge_cost = gen_array_make(0);
        gen_array_addto(annotations, ordering, item); 
      }
      else { 
        item = gen_array_item(annotations, ordering);
        if(item->edge_cost == NULL)
          item->edge_cost = gen_array_make(0);
        double *ec = (double *)malloc(sizeof(double));
        *ec = cost;
        gen_array_addto(item->edge_cost, ordering2, ec);
        gen_array_addto(annotations, ordering, item);
      }
     
    }    
  fclose(finstrumented);  
  return;
}

References annotations, dg, annotation::edge_cost, file_name, FOREACH, gen_array_addto(), gen_array_item(), gen_array_make(), graph_vertices, malloc(), statement_ordering, statement_to_vertex(), SUCCESSOR, successor_vertex, annotation::task_time, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by dsc_code_parallelization(), and hbdsc_parallelization().

Here is the call graph for this function:

Here is the caller graph for this function:

polynomial_to_numerical()

double polynomial_to_numerical

(

Ppolynome

poly_amount

)

if polynomial is not a constant monomial, we use
an heuristic to map it into a numerical constant take the higher degree monomial and decide upon its coefficient

Parameters

poly_amount

oly_amount

Definition at line 93 of file cost_model.c.

{
   double size = 0.f;
   /* if polynomial is not a constant monomial, we use    
    * an heuristic to map it into a numerical constant 
    * take the higher degree monomial
    * and decide upon its coefficient
    */
   if(!POLYNOME_UNDEFINED_P(poly_amount))
     {
       int max_degree = polynome_max_degree(poly_amount);
       for(Ppolynome p = poly_amount; !POLYNOME_NUL_P(p); p = polynome_succ(p)) {
         int curr_degree =  (int)vect_sum(monome_term(polynome_monome(p)));
         if(curr_degree == max_degree) {
           size = monome_coeff(polynome_monome(p));
           break;
         }
       }
     }
   return size;
}

References int, monome_coeff, monome_term, polynome_max_degree(), polynome_monome, POLYNOME_NUL_P, polynome_succ, POLYNOME_UNDEFINED_P, and vect_sum().

Referenced by edge_cost(), size_of_regions(), and task_time().

Here is the call graph for this function:

Here is the caller graph for this function:

priorities()

void priorities

(

gen_array_t

annotations

)

Parameters

annotations

nnotations

Definition at line 253 of file cost_model.c.

{
  size_t i;
  for(i = 0; i< gen_array_nitems(annotations); i++){
    if(gen_array_item(annotations, i) != NULL){
      annotation *item = gen_array_item(annotations, i);
      item->prio = item->tlevel + item->blevel;
      gen_array_addto(annotations, i, item);
    }
  }
  return;
}

References annotations, annotation::blevel, gen_array_addto(), gen_array_item(), gen_array_nitems(), annotation::prio, and annotation::tlevel.

Referenced by BDSC(), and DSC().

Here is the call graph for this function:

Here is the caller graph for this function:

size_of_regions()

double size_of_regions

(

list

l_data

)

Parameters

l_data

_data

Definition at line 115 of file cost_model.c.

{
  Ppolynome transfer_time = POLYNOME_NUL;
  FOREACH(REGION,reg,l_data){
    Ppolynome reg_footprint= region_enumerate(reg); 
    reg_footprint = polynome_mult(reg_footprint, expression_to_polynome(int_to_expression(SizeOfElements(variable_basic(type_variable(entity_type(region_entity(reg))))))));
    polynome_add(&transfer_time, reg_footprint);
  }   
  return polynomial_to_numerical(transfer_time); 
}

References entity_type, expression_to_polynome(), FOREACH, int_to_expression(), polynome_add(), polynome_mult(), POLYNOME_NUL, polynomial_to_numerical(), REGION, region_entity, region_enumerate(), SizeOfElements(), type_variable, and variable_basic.

Referenced by MCW(), and transfer_cost().

Here is the call graph for this function:

Here is the caller graph for this function:

t_level()

double t_level	(	vertex	v,
		graph	dg,
		gen_array_t	annotations
	)

First parameter is the top level (earliest start time) for each node.

intptr_t)

Parameters

dg	g
annotations	nnotations

Definition at line 168 of file cost_model.c.

{
  double max = 0, level;
  list vertices = (graph_vertices(dg));
  annotation *an,*anp;
  statement sv = vertex_to_statement(v);
  FOREACH(VERTEX, pre, vertices) {
    statement parent = vertex_to_statement(pre);
      FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
        vertex s = successor_vertex(su);
        statement child = vertex_to_statement(s);
        if(statement_equal_p(child, sv) && !statement_equal_p(child,parent) && gen_array_item(annotations, (int)statement_ordering(parent))){       
          double tl_p;
          anp = gen_array_item(annotations, (int)statement_ordering(parent));
          double edge_c = *(double *)/*(intptr_t)*/(gen_array_item(anp->edge_cost, statement_ordering(sv)));
          if(anp->tlevel != -1)
            tl_p = anp->tlevel;
          else
            tl_p =  t_level(pre, dg, annotations);
          level = tl_p + anp->task_time + edge_c ;
          if(level > max)
            max = level;
        }
        else {
          if(statement_equal_p(child, sv) && !statement_equal_p(child,parent) && gen_array_item(annotations, (int)statement_ordering(parent))==NULL )
            {
              anp = gen_array_item(annotations, (int)statement_ordering(parent));
              double edge_c = *(double *)(gen_array_item(anp->edge_cost,statement_ordering(sv)));
              level = t_level(pre, dg, annotations) + anp->task_time + edge_c;
              if(level > max)
                max = level;
            }
        }
      }
  }
  if((int)statement_ordering(sv) < (int) gen_array_size(annotations) && gen_array_item(annotations, (int)statement_ordering(sv))!=NULL)
    an = gen_array_item(annotations, statement_ordering(sv));
  else
    an = (annotation *)malloc(sizeof(annotation));
  an->tlevel = max;
  gen_array_addto(annotations, (int)statement_ordering(sv), an);
  return max; 
}

References annotations, dg, annotation::edge_cost, FOREACH, gen_array_addto(), gen_array_item(), gen_array_size(), graph_vertices, level, malloc(), max, statement_equal_p(), statement_ordering, SUCCESSOR, successor_vertex, annotation::task_time, annotation::tlevel, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by top_level(), and update_priority_values().

Here is the call graph for this function:

Here is the caller graph for this function:

task_time()

static double task_time ( statement  s )

static

Definition at line 134 of file cost_model.c.

{
  complexity stat_comp = load_statement_complexity(s);
  Ppolynome poly = complexity_polynome(stat_comp);
  return polynomial_to_numerical(poly);
}

References complexity_polynome(), load_statement_complexity(), and polynomial_to_numerical().

Referenced by hierarchical_schedule_step(), and initialization().

Here is the call graph for this function:

Here is the caller graph for this function:

top_level()

void top_level	(	graph	dg,
		gen_array_t	annotations
	)

Parameters

dg	g
annotations	nnotations

Definition at line 211 of file cost_model.c.

{
  list vertices = graph_vertices(dg);
  FOREACH(VERTEX, v, vertices){ 
    t_level(v, dg, annotations);
  }
  return; 
}

References annotations, dg, FOREACH, graph_vertices, t_level(), and VERTEX.

Referenced by BDSC(), and DSC().

Here is the call graph for this function:

Here is the caller graph for this function:

used_data()

static list used_data ( statement(st)  )

static

Definition at line 126 of file cost_model.c.

                                    {
  list l_data = NIL;
  list l_read = regions_dup(regions_read_regions(load_statement_local_regions(st)));  
  list l_write = regions_dup(regions_write_regions(load_statement_local_regions(st)));
  l_data =  RegionsMustUnion(regions_dup(l_read), regions_dup(l_write), r_w_combinable_p);
  return l_data;
}

References load_statement_local_regions(), NIL, r_w_combinable_p(), regions_dup(), regions_read_regions(), regions_write_regions(), and RegionsMustUnion().

Referenced by initialization().

Here is the call graph for this function:

Here is the caller graph for this function: