HBDSC.c File Reference

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "boolean.h"
#include <stdbool.h>
#include <limits.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 "conversion.h"
#include "properties.h"
#include "semantics.h"
#include "transformations.h"
#include "effects-convex.h"
#include "complexity_ri.h"
#include "complexity.h"
#include "dg.h"
#include "graph.h"
#include "ricedg.h"
#include "chains.h"
#include "task_parallelization.h"

Include dependency graph for HBDSC.c:

Go to the source code of this file.

Macros
#define	MAX_ITER   1

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

Functions
static gen_array_t	schedule_failsafe ()
static void	cancel_schedule (gen_array_t annotations_s, list stmts)
static void	cancel_schedule_stmt (gen_array_t annotations_s, statement st)
static double	critical_path_length (int nbclusters)
static void	initialization_clusters (bool first_p)
	eset to zero for each new sequence to handle More...
static list	rebuild_topological_sort (list stages)
list	topological_sort (statement stmt)
static double	transfer_cost (statement s, int nbclusters)
static void	hierarchical_schedule_step (statement stmt, int P, int M, bool dsc_p)
int	hierarchical_schedule (statement stmt, int k, int P, int M, bool dsc_p)
bool	hbdsc_parallelization (char *module_name)
	he main function for performing the hierarchical scheduling (scheduled SDG) using BDSC and generating the graph (unstructured) BDSC-based top-down hierarchical scheduling More...
bool	dsc_code_parallelization (char *module_name)
	he main function for performing the hierarchical scheduling (scheduled SDG) using DSC and generating SPIRE More...

Variables
graph	kdg
	Global variables. More...
graph	ddg
statement	return_st = statement_undefined
persistant_statement_to_cluster	stmt_to_cluster

Macro Definition Documentation

MAX_ITER

#define MAX_ITER   1

Definition at line 54 of file HBDSC.c.

Typedef Documentation

arc_label

typedef dg_arc_label arc_label

Instantiation of the dependence graph:

Definition at line 43 of file HBDSC.c.

vertex_label

typedef dg_vertex_label vertex_label

Definition at line 44 of file HBDSC.c.

Function Documentation

cancel_schedule()

static void cancel_schedule ( gen_array_t  annotations_s, list  stmts  )

static

Definition at line 79 of file HBDSC.c.

{
  FOREACH(STATEMENT, s,  stmts){
    annotation *vs = gen_array_item(annotations_s,(int)statement_ordering(s));
    annotation *item = gen_array_item(annotations,(int)statement_ordering(s));
    item->scheduled = vs->scheduled;
    item->cluster = vs->cluster;
    if(bound_persistant_statement_to_cluster_p(stmt_to_cluster, statement_ordering(s)))
      update_persistant_statement_to_cluster(stmt_to_cluster, statement_ordering(s), item->cluster);
    item->edge_cost = vs->edge_cost;
    gen_array_addto(annotations, (int)statement_ordering(s), item);
  }
  return;
}

References annotations, bound_persistant_statement_to_cluster_p(), annotation::cluster, annotation::edge_cost, FOREACH, gen_array_addto(), gen_array_item(), annotation::scheduled, STATEMENT, statement_ordering, stmt_to_cluster, and update_persistant_statement_to_cluster().

Referenced by cancel_schedule_stmt(), and hierarchical_schedule().

Here is the call graph for this function:

Here is the caller graph for this function:

cancel_schedule_stmt()

static void cancel_schedule_stmt ( gen_array_t  annotations_s, statement  st  )

static

Definition at line 93 of file HBDSC.c.

{
  instruction inst = statement_instruction(st);
  switch(instruction_tag(inst)){
  case is_instruction_block:
    cancel_schedule(annotations_s,sequence_statements(statement_sequence(st)));
    break;
  case is_instruction_loop:
    cancel_schedule_stmt(annotations_s, loop_body(statement_loop(st)));
    break;
  default:
    break;
  }
  return; 
}

References cancel_schedule(), instruction_tag, is_instruction_block, is_instruction_loop, loop_body, sequence_statements, statement_instruction, statement_loop(), and statement_sequence().

Referenced by hierarchical_schedule_step().

Here is the call graph for this function:

Here is the caller graph for this function:

critical_path_length()

static double critical_path_length ( int  nbclusters )

static

Definition at line 108 of file HBDSC.c.

                                                  {
  double max = -1;
  int cl;
  for(cl = 0; cl < nbclusters; cl++)
    {
      cluster *cl_s = gen_array_item(clusters, cl);
      double time = cl_s->time;
      if(time > max) 
        max = time;
    }
  return max;
}

References clusters, gen_array_item(), max, and cluster::time.

Referenced by hierarchical_schedule().

Here is the call graph for this function:

Here is the caller graph for this function:

dsc_code_parallelization()

bool dsc_code_parallelization

(

char *

module_name

)

he main function for performing the hierarchical scheduling (scheduled SDG) using DSC and generating SPIRE

The proper effect to detect the I/O operations:

omplexities (task processing time)

roperties to set the parameters of BDSC

ost model generation

SC-based top-down hierarchical scheduling

Reorder the module, because new statements have been generated.

Parameters

module_name

odule_name

Definition at line 473 of file HBDSC.c.

{ 
  statement     module_stat;
  if (!get_bool_property("COMPLEXITY_EARLY_EVALUATION")) 
    set_bool_property("COMPLEXITY_EARLY_EVALUATION", true);
  module_stat = (statement)db_get_memory_resource(DBR_CODE, module_name, true);
  set_ordering_to_statement(module_stat);
  set_current_module_entity(module_name_to_entity(module_name));
  set_current_module_statement(module_stat);
  set_precondition_map((statement_mapping)db_get_memory_resource(DBR_PRECONDITIONS, module_name, true));
  set_transformer_map((statement_mapping)
                      db_get_memory_resource(DBR_TRANSFORMERS, module_name, true));
  /* The proper effect to detect the I/O operations: */
  set_proper_rw_effects((statement_effects)db_get_memory_resource(DBR_PROPER_EFFECTS, module_name, true));
   set_cumulated_rw_effects((statement_effects)db_get_memory_resource(DBR_CUMULATED_EFFECTS, module_name, true));
  module_to_value_mappings(get_current_module_entity());
  set_rw_effects((statement_effects) 
                 db_get_memory_resource(DBR_REGIONS, module_name, true));
  set_in_effects((statement_effects) db_get_memory_resource(DBR_IN_REGIONS, module_name, true));
  set_out_effects((statement_effects) db_get_memory_resource(DBR_OUT_REGIONS, module_name, true));
  set_methods_for_convex_effects();
  init_convex_rw_prettyprint(module_name);
 
  kdg = (graph) db_get_memory_resource (DBR_DG, module_name, true );
  
  /*Complexities (task processing time)*/
  set_complexity_map( (statement_mapping) db_get_memory_resource(DBR_COMPLEXITIES, module_name, true));
 
  /*Properties to set the parameters of BDSC*/
  NBCLUSTERS = 1;//INT_MAX;
  MEMORY_SIZE = -1;
  INSTRUMENTED_FILE = strdup(get_string_property("BDSC_INSTRUMENTED_FILE"));
  /*cost model generation */
  annotations = gen_array_make(0);
  clusters = gen_array_make(0);
  if(sizeof(INSTRUMENTED_FILE) == 8)
    initialization(kdg, annotations);
  else
    parse_instrumented_file(INSTRUMENTED_FILE, kdg, annotations);
 
  stmt_to_cluster = make_persistant_statement_to_cluster();
  /*DSC-based top-down hierarchical scheduling*/
  hierarchical_schedule(module_stat, 0, NBCLUSTERS, MEMORY_SIZE, true);
  /* Reorder the module, because new statements have been generated. */
  module_reorder(module_stat);
  DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, module_stat);
  reset_ordering_to_statement();
  reset_current_module_statement();
  reset_current_module_entity();
  reset_proper_rw_effects();
  reset_cumulated_rw_effects();
  reset_rw_effects();
  reset_in_effects();
  reset_out_effects();
  reset_precondition_map();
  reset_complexity_map();
  reset_transformer_map();
  gen_array_free(annotations);
  gen_array_free(clusters);
  generic_effects_reset_all_methods();
  free_value_mappings();
  return true;
}

References annotations, clusters, db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, free_value_mappings(), gen_array_free(), gen_array_make(), generic_effects_reset_all_methods(), get_bool_property(), get_current_module_entity(), get_string_property(), hierarchical_schedule(), init_convex_rw_prettyprint(), initialization(), INSTRUMENTED_FILE, kdg, make_persistant_statement_to_cluster(), MEMORY_SIZE, module_name(), module_name_to_entity(), module_reorder(), module_to_value_mappings(), NBCLUSTERS, parse_instrumented_file(), reset_complexity_map(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_in_effects(), reset_ordering_to_statement(), reset_out_effects(), reset_precondition_map(), reset_proper_rw_effects(), reset_rw_effects(), reset_transformer_map(), set_bool_property(), set_complexity_map(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_in_effects(), set_methods_for_convex_effects(), set_ordering_to_statement(), set_out_effects(), set_precondition_map(), set_proper_rw_effects(), set_rw_effects(), set_transformer_map(), stmt_to_cluster, and strdup().

Here is the call graph for this function:

hbdsc_parallelization()

bool hbdsc_parallelization

(

char *

module_name

)

he main function for performing the hierarchical scheduling (scheduled SDG) using BDSC and generating the graph (unstructured) BDSC-based top-down hierarchical scheduling

The proper effect to detect the I/O operations:

omplexities (task processing time)

roperties to set the parameters of BDSC

ost model generation

Parameters

module_name

odule_name

Definition at line 396 of file HBDSC.c.

{ 
  statement     module_stat;
  string tg_name = NULL;
  FILE *ftg;
  if (!get_bool_property("COMPLEXITY_EARLY_EVALUATION")) 
    set_bool_property("COMPLEXITY_EARLY_EVALUATION", true);
  module_stat = (statement)db_get_memory_resource(DBR_CODE, module_name, true);
  set_ordering_to_statement(module_stat);
  set_current_module_entity(module_name_to_entity(module_name));
  set_current_module_statement(module_stat);
  set_precondition_map((statement_mapping)db_get_memory_resource(DBR_PRECONDITIONS, module_name, true));
  set_transformer_map((statement_mapping)
                      db_get_memory_resource(DBR_TRANSFORMERS, module_name, true));
  /* The proper effect to detect the I/O operations: */
  set_proper_rw_effects((statement_effects)db_get_memory_resource(DBR_PROPER_EFFECTS, module_name, true));
  set_cumulated_rw_effects((statement_effects)db_get_memory_resource(DBR_CUMULATED_EFFECTS, module_name, true));
  module_to_value_mappings(get_current_module_entity());
  set_rw_effects((statement_effects) 
                 db_get_memory_resource(DBR_REGIONS, module_name, true));
  set_in_effects((statement_effects) db_get_memory_resource(DBR_IN_REGIONS, module_name, true));
  set_out_effects((statement_effects) db_get_memory_resource(DBR_OUT_REGIONS, module_name, true));
  set_methods_for_convex_effects();
  init_convex_rw_prettyprint(module_name);
  kdg = (graph) db_get_memory_resource (DBR_SDG, module_name, true );
  /*Complexities (task processing time)*/
  set_complexity_map( (statement_mapping) db_get_memory_resource(DBR_COMPLEXITIES, module_name, true));
  /*Properties to set the parameters of BDSC*/
  NBCLUSTERS = get_int_property("BDSC_NB_CLUSTERS");
  MEMORY_SIZE = get_int_property("BDSC_MEMORY_SIZE");
  INSTRUMENTED_FILE = strdup(get_string_property("BDSC_INSTRUMENTED_FILE"));
 
  /*cost model generation */
  annotations = gen_array_make(0);
  clusters = gen_array_make(0);
  initialization_clusters(true);
  if(strlen(INSTRUMENTED_FILE) == 0)
    initialization(kdg, annotations);
  else
    parse_instrumented_file(INSTRUMENTED_FILE, kdg, annotations);
  stmt_to_cluster = make_persistant_statement_to_cluster();
  hierarchical_schedule(module_stat, 0, NBCLUSTERS, MEMORY_SIZE, false);
  tg_name = strdup(concatenate(db_get_current_workspace_directory(),
                               "/",module_name,"/",module_name, "_scheduled_sdg.dot", NULL));
  ftg = safe_fopen(tg_name, "w");
  fprintf( ftg, "digraph {\n compound=true;ratio=fill; node[fontsize=24,fontname=\"Courier\",labelloc=\"t\"];nodesep=.05;\n" );
  print_SDGs(module_stat, kdg, ftg, annotations);
  fprintf( ftg, "\n}\n" );
  safe_fclose(ftg, tg_name);
  free(tg_name);
  
  DB_PUT_MEMORY_RESOURCE(DBR_SDG, module_name, (char*) kdg);
  gen_consistent_p((gen_chunk*)stmt_to_cluster);
  DB_PUT_MEMORY_RESOURCE(DBR_SCHEDULE, module_name, (char*) stmt_to_cluster);
  reset_proper_rw_effects();
  reset_cumulated_rw_effects();
  reset_ordering_to_statement();
  reset_rw_effects();
  reset_in_effects();
  reset_out_effects();
  reset_precondition_map();
  reset_complexity_map();
  reset_transformer_map();
  reset_current_module_statement();
  reset_current_module_entity();
  gen_array_full_free(annotations);
  gen_array_full_free(clusters);
  generic_effects_reset_all_methods();
  free_value_mappings();
  return true;
}

References annotations, clusters, concatenate(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, fprintf(), free(), free_value_mappings(), gen_array_full_free(), gen_array_make(), gen_consistent_p(), generic_effects_reset_all_methods(), get_bool_property(), get_current_module_entity(), get_int_property(), get_string_property(), hierarchical_schedule(), init_convex_rw_prettyprint(), initialization(), initialization_clusters(), INSTRUMENTED_FILE, kdg, make_persistant_statement_to_cluster(), MEMORY_SIZE, module_name(), module_name_to_entity(), module_to_value_mappings(), NBCLUSTERS, parse_instrumented_file(), print_SDGs(), reset_complexity_map(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_in_effects(), reset_ordering_to_statement(), reset_out_effects(), reset_precondition_map(), reset_proper_rw_effects(), reset_rw_effects(), reset_transformer_map(), safe_fclose(), safe_fopen(), set_bool_property(), set_complexity_map(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_in_effects(), set_methods_for_convex_effects(), set_ordering_to_statement(), set_out_effects(), set_precondition_map(), set_proper_rw_effects(), set_rw_effects(), set_transformer_map(), stmt_to_cluster, and strdup().

hierarchical_schedule()

int hierarchical_schedule	(	statement	stmt,
		int	k,
		int	P,
		int	M,
		bool	dsc_p
	)

Definition at line 311 of file HBDSC.c.

{
  int nbclusters = 0, nbcl; double cpl;
  if(!get_bool_property("COSTLY_TASKS_ONLY") | costly_task(stmt)){ //granularity management
    instruction inst = statement_instruction(stmt);
    annotation *item = gen_array_item(annotations,(int)statement_ordering(stmt));
    switch(instruction_tag(inst))
      {
      case is_instruction_block:{
        sequence seq = statement_sequence(stmt);
        if(gen_length(sequence_statements(seq))>0){
          gen_array_t annotations_i = schedule_failsafe(), annotations_s;
          if(!dsc_p)
            nbcl = BDSC(seq, P, M, statement_ordering(stmt));
          else{
            nbcl = DSC(seq, statement_ordering(stmt));
            NBCLUSTERS = NBCLUSTERS > nbcl ? NBCLUSTERS:nbcl;
          }
          double cpl1 = critical_path_length(nbcl);
          int iter = 0;
          
          do{
            hierarchical_schedule_step(stmt, P, M, dsc_p);
            nbclusters = nbcl;
            cpl = cpl1;
            annotations_s = schedule_failsafe();
            cancel_schedule(annotations_i, sequence_statements(seq));
            if(!dsc_p){
              nbcl = BDSC(seq, P, M, statement_ordering(stmt));
            }
            else{
              nbcl = DSC(seq, statement_ordering(stmt));
              NBCLUSTERS = NBCLUSTERS > nbcl ? NBCLUSTERS:nbcl;
            }
            cpl1 = critical_path_length(nbcl); 
            if(nbcl == 0){ 
              fprintf (stderr, "Unable to schedule with NBCLUSTERS  equal to %d\n",P);
              exit (EXIT_FAILURE);
            }
            if(nbcl == -1){ 
              fprintf (stderr, "Unable to schedule with MEMORY SIZE  equal to %d\n",M);
              exit (EXIT_FAILURE);
            }
            iter ++;
          } while(cpl1 < cpl && nbcl <= nbclusters && iter <= MAX_ITER);
          cancel_schedule(annotations_s, sequence_statements(seq));
          item->task_time = cpl;
          item->data = NIL;
          gen_array_free(annotations_i);
          gen_array_free(annotations_s);
        }
        break;
      }
      case is_instruction_test : {
        test t = instruction_test(inst);
        int nbt = hierarchical_schedule(test_true(t), k, P, M, dsc_p);
        int nbf = hierarchical_schedule(test_false(t), k, P, M, dsc_p);
        nbclusters = nbt > nbf? nbt: nbf; 
        break;
      }
      case is_instruction_loop :{
        loop l = statement_loop(stmt);
        statement body = loop_body(l);
        nbclusters = hierarchical_schedule(body, k, P, M, dsc_p);
        break;
      }
      case is_instruction_forloop :{
        forloop l = statement_forloop(stmt);
        statement body = forloop_body(l);
        nbclusters = hierarchical_schedule(body, k, P, M, dsc_p);
        break;
      }
      default:
        break;
      }
    item->nbclusters = nbclusters;
    allocate_task_to_cluster(stmt, k, 0);
  }
  return nbclusters;
}

References allocate_task_to_cluster(), annotations, BDSC(), cancel_schedule(), costly_task(), critical_path_length(), annotation::data, DSC(), exit, EXIT_FAILURE, forloop_body, fprintf(), gen_array_free(), gen_array_item(), gen_length(), get_bool_property(), hierarchical_schedule_step(), instruction_tag, instruction_test, is_instruction_block, is_instruction_forloop, is_instruction_loop, is_instruction_test, loop_body, MAX_ITER, NBCLUSTERS, annotation::nbclusters, NIL, schedule_failsafe(), sequence_statements, statement_forloop(), statement_instruction, statement_loop(), statement_ordering, statement_sequence(), annotation::task_time, test_false, and test_true.

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

Here is the call graph for this function:

Here is the caller graph for this function:

hierarchical_schedule_step()

static void hierarchical_schedule_step ( statement  stmt, int  P, int  M, bool  dsc_p  )

static

Definition at line 274 of file HBDSC.c.

{
  list cluster_stages  = topological_sort(stmt);
  int nbclustersL, nbclusters, nbclusters_s;
  double task_time, task_time_s;
  FOREACH(LIST, cluster_stage, cluster_stages) {
    int stage_mod = gen_length(cluster_stage);
    int Ps = P - stage_mod;// + 1;//use current processor
    FOREACH(LIST, L, cluster_stage){
      nbclustersL = 0;
      FOREACH(statement, st, L){
        if(Ps <= 0){
          pips_user_warning("NBCLUSTERS is not sufficient to handle nested parts in statement_ordering = %d\n", statement_ordering(st));
        }
        else{
        if(!get_bool_property("COSTLY_TASKS_ONLY") | costly_task(st)){
          annotation *item = gen_array_item(annotations,(int)statement_ordering(st));
          nbclusters = item->nbclusters;
          task_time = item->task_time;
          gen_array_t annotations_s = schedule_failsafe();
          nbclusters_s = hierarchical_schedule(st, (item->cluster == -1)?0:item->cluster, Ps, M, dsc_p);
          item = gen_array_item(annotations,(int)statement_ordering(st));
          task_time_s = item->task_time;
          if(nbclusters_s < nbclusters || task_time + transfer_cost(st, nbclusters) < task_time_s + transfer_cost(st, nbclusters_s)){
            item->nbclusters = nbclusters;
            cancel_schedule_stmt(annotations_s,st);
          }
          nbclustersL = nbclustersL > nbclusters? nbclustersL : nbclusters; 
          gen_array_free(annotations_s);
        }
        }
      }
      Ps = Ps - nbclustersL;
    }
  }
  return;
}

References annotations, cancel_schedule_stmt(), annotation::cluster, costly_task(), FOREACH, gen_array_free(), gen_array_item(), gen_length(), get_bool_property(), hierarchical_schedule(), LIST, annotation::nbclusters, pips_user_warning, schedule_failsafe(), statement_ordering, task_time(), annotation::task_time, topological_sort(), and transfer_cost().

Referenced by hierarchical_schedule().

Here is the call graph for this function:

Here is the caller graph for this function:

initialization_clusters()

static void initialization_clusters ( bool  first_p )

static

eset to zero for each new sequence to handle

Definition at line 122 of file HBDSC.c.

{
  int i;
  cluster *cl_s;
  for(i=0;i<NBCLUSTERS;i++){
    if(first_p)
      cl_s = (cluster *)malloc(sizeof(cluster));
    else
      cl_s = gen_array_item(clusters, i);
    cl_s->time = 0;
    cl_s->data = NIL;
    gen_array_addto(clusters, i, cl_s);
  }
  return; 
}

References clusters, cluster::data, gen_array_addto(), gen_array_item(), malloc(), NBCLUSTERS, NIL, and cluster::time.

Referenced by hbdsc_parallelization().

Here is the call graph for this function:

Here is the caller graph for this function:

rebuild_topological_sort()

static list rebuild_topological_sort ( list  stages )

static

we suppose that we have only one return statement at the end of the module :(

Definition at line 146 of file HBDSC.c.

                                                 {
  list K = NIL, cluster_stages = NIL;
  int i;
  FOREACH(LIST, stage, stages) {
    K=NIL;
    for(i = 0; i < NBCLUSTERS; i++){
      list list_stmts = NIL;
      FOREACH(STATEMENT, st, stage) {
        if(!declaration_statement_p(st) && !return_statement_p(st)) {
          if(bound_persistant_statement_to_cluster_p(stmt_to_cluster,statement_ordering(st))){
            if(apply_persistant_statement_to_cluster(stmt_to_cluster, statement_ordering(st)) == i)
              list_stmts = CONS(STATEMENT, st, list_stmts);
          }
        }
        /* we suppose that we have only one return statement at the
          end of the module :( */
        if(return_statement_p(st))
          return_st = st;
      }
      if(list_stmts != NIL)
        K = CONS(LIST, list_stmts, K);
    }
    if(K == NIL){
      list list_stmts = NIL;
      FOREACH(STATEMENT, st, stage) {
        if(!declaration_statement_p(st) && !return_statement_p(st)) {
          if(bound_persistant_statement_to_cluster_p(stmt_to_cluster,statement_ordering(st))){
            if(apply_persistant_statement_to_cluster(stmt_to_cluster, statement_ordering(st)) == -1) 
              list_stmts = CONS(STATEMENT, st, list_stmts);
          }
          else
            list_stmts = CONS(STATEMENT, st, list_stmts);
        }
        if(return_statement_p(st))
          return_st = st;
      }
      if(list_stmts != NIL){
        K =  CONS(LIST, list_stmts, K);
      }
    }
    if(K != NIL)
      cluster_stages = CONS(LIST, gen_nreverse(K), cluster_stages);
  }
  return cluster_stages;
}

References apply_persistant_statement_to_cluster(), bound_persistant_statement_to_cluster_p(), CONS, declaration_statement_p(), FOREACH, gen_nreverse(), LIST, NBCLUSTERS, NIL, return_st, return_statement_p(), STATEMENT, statement_ordering, and stmt_to_cluster.

Referenced by topological_sort().

Here is the call graph for this function:

Here is the caller graph for this function:

schedule_failsafe()

static gen_array_t schedule_failsafe ( )

static

Definition at line 59 of file HBDSC.c.

                                      {
  gen_array_t annotations_s = gen_array_make(0);
  FOREACH(VERTEX, v,  graph_vertices(kdg)){
    statement s = vertex_to_statement(v);
    annotation *item = (annotation *)malloc(sizeof(annotation)); 
    annotation *vs = gen_array_item(annotations,(int)statement_ordering(s));
    item->scheduled = vs->scheduled;
    item->cluster = vs->cluster;
    item->edge_cost = gen_array_make(gen_length(vertex_successors(v)));
    FOREACH(SUCCESSOR, su, (vertex_successors(v))){
      vertex s = successor_vertex(su);
      statement child = vertex_to_statement(s);
      gen_array_addto(item->edge_cost, statement_ordering(child), gen_array_item(vs->edge_cost,statement_ordering(child)));
    }
    gen_array_addto(annotations_s, (int)statement_ordering(s), item); 
  }
  return annotations_s;
}

References annotations, annotation::cluster, annotation::edge_cost, FOREACH, gen_array_addto(), gen_array_item(), gen_array_make(), gen_length(), graph_vertices, kdg, malloc(), annotation::scheduled, statement_ordering, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by hierarchical_schedule(), and hierarchical_schedule_step().

Here is the call graph for this function:

Here is the caller graph for this function:

topological_sort()

list topological_sort

(

statement

stmt

)

Parameters

stmt

tmt

Definition at line 192 of file HBDSC.c.

{
  list K = NIL; uint i;
  list cluster_stages = NIL;
  list vertices = graph_vertices(kdg);
  gen_array_t I = gen_array_make(0);
  for(i = 0;i<gen_length(vertices);i++){
      gen_array_addto(I, i, 0);
  }
  FOREACH(statement, st, sequence_statements(statement_sequence(stmt))){ 
    FOREACH(VERTEX, v, vertices) {
      statement parent = vertex_to_statement(v);
      if(statement_equal_p(st,parent)){
        FOREACH(SUCCESSOR, su, (vertex_successors(v))) {
          vertex w = successor_vertex(su);
          statement child = vertex_to_statement(w);
          gen_array_addto(I, (int)statement_ordering(child), gen_array_item(I, (int)statement_ordering(child)) + 1);
        }
      }
    }
  }
  FOREACH(statement, st, sequence_statements(statement_sequence(stmt))){
    if(gen_array_item(I, statement_ordering(st)) == 0)
      K = CONS(STATEMENT, st, K);
  }
  list L =  gen_copy_seq(K);
  cluster_stages = CONS(LIST, L, cluster_stages);
  bool insert_p = false;
  while(K != NIL){
    statement st = STATEMENT(CAR(gen_last(K)));
    gen_remove_once(&K, st);
    FOREACH(VERTEX, pre, vertices) { 
      statement parent = vertex_to_statement(pre);
      if(statement_equal_p(parent, st)){
          FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
            vertex v = successor_vertex(su);
            statement child = vertex_to_statement(v);
            gen_array_addto(I, (int)statement_ordering(child), gen_array_item(I, (int)statement_ordering(child)) - 1);
            if(gen_array_item(I, statement_ordering(child)) == 0 && gen_occurences(child, K) == 0) {
              K = CONS(STATEMENT, child, K);
              insert_p = true;
            }
          }
          break;
      }
    }
    list M = NIL;
    bool ins_p = true,found_p=false;
    FOREACH(STATEMENT, stmt, K){
      found_p = false;
      FOREACH(STATEMENT, stmtl, L){
        if(statement_equal_p(stmt,stmtl))
          found_p = true;
      }
      if(!found_p)
        M = CONS(STATEMENT,stmt,M);
      else{
        ins_p = false;
        found_p = false;
      }
    }
    if( ins_p && gen_length(M) > 0 && insert_p){
      cluster_stages = CONS(LIST, M, cluster_stages);
      insert_p = false;
      L =  gen_copy_seq(K);
    }
  }
  gen_array_free(I);
  return rebuild_topological_sort(cluster_stages);
}

References CAR, CONS, FOREACH, gen_array_addto(), gen_array_free(), gen_array_item(), gen_array_make(), gen_copy_seq(), gen_last(), gen_length(), gen_occurences(), gen_remove_once(), graph_vertices, kdg, LIST, NIL, rebuild_topological_sort(), sequence_statements, STATEMENT, statement_equal_p(), statement_ordering, statement_sequence(), SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by cluster_stage_spire_generation(), and hierarchical_schedule_step().

Here is the call graph for this function:

Here is the caller graph for this function:

transfer_cost()

static double transfer_cost ( statement  s, int  nbclusters  )

static

Definition at line 264 of file HBDSC.c.

                                                        {
  if(nbclusters == 0 || !get_bool_property("BDSC_DISTRIBUTED_MEMORY"))
    return 0;
  list l_in = regions_dup(load_statement_in_regions(s));
  list l_out = regions_dup(load_statement_out_regions(s));
  double size = size_of_regions(l_in) + size_of_regions(l_out);
  return size;
}

References get_bool_property(), load_statement_in_regions(), load_statement_out_regions(), regions_dup(), and size_of_regions().

Referenced by hierarchical_schedule_step().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

ddg

graph ddg

Definition at line 52 of file HBDSC.c.

Referenced by sequence_dependence_graph().

kdg

graph kdg

Global variables.

HBDSC.c.

Definition at line 52 of file HBDSC.c.

Referenced by allocate_task_to_cluster(), BDSC(), bdsc_code_instrumentation(), DSC(), dsc_code_parallelization(), end_idle_clusters(), hbdsc_parallelization(), MCW(), move_task_to_cluster(), ready_node(), schedule_failsafe(), spire_distributed_unstructured_to_structured(), spire_shared_unstructured_to_structured(), tlevel_decrease(), topological_sort(), update_priority_values(), and zeroing_multiple_edges().

return_st

statement return_st = statement_undefined

Definition at line 53 of file HBDSC.c.

Referenced by gen_omp_parallel(), mpi_finalize(), mpi_initialize(), openmp_task_generation(), rebuild_topological_sort(), spire_distributed_unstructured_to_structured(), and spire_shared_unstructured_to_structured().

stmt_to_cluster

persistant_statement_to_cluster stmt_to_cluster

Definition at line 56 of file HBDSC.c.

Referenced by allocate_task_to_cluster(), cancel_schedule(), cluster_stage_spire(), cluster_stage_spire_generation(), dsc_code_parallelization(), hbdsc_parallelization(), move_task_to_cluster(), rebuild_topological_sort(), spire_distributed_unstructured_to_structured(), and spire_shared_unstructured_to_structured().