BDSC.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 BDSC.c:

Go to the source code of this file.

Data Structures
struct	min_start_time
	Global variables. More...

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

Functions
static bool	ready_node (statement st)
static void	update_priority_values (statement ready_st)
void	allocate_task_to_cluster (statement ready_st, int cl_p, int order)
	BDSC.c. More...
static void	move_task_to_cluster (statement ready_st, int cl_p)
static bool	MCW (statement ready_st, int cl, int M)
static min_start_time	tlevel_decrease (statement ready_st, int M)
static bool	zeroing_multiple_edges (statement ready_st, int order, int M)
static int	end_idle_clusters (statement ready_st, int nbclusters)
	pply the second priority : load balancing : length_cluster(c_i) < tlevel(ready_st) and forall node n_y in c_i scheduled(successors(n_y)) = true or successors(n_y) \subset successors(ready_st) More...
static int	min_start_time_cluster (int nbclusters)
	pply the third priority if bounded number of processors is exceeded start-time(ready_st) = min(length_cluster(c_i)) tlevel(ready_st) can be increased. More...
static double	max_start_time_cluster (int nbclusters)
	sed to compute the parallel task time of a task More...
static bool	DSRW (statement ready_st, statement unready_st, int order, int M)
static statement	select_task_with_highest_priority (list tasks, statement ready)
static gen_array_t	schedule_failsafe ()
static void	cancel_schedule (gen_array_t annotations_s, list stmts)
static void	initialization_clusters (bool first_p)
	eset to zero for each new sequence to handle More...
static void	update_parallel_task (int ordering, int nbclusters)
static int	find_cluster (statement ready_task, int nbclusters, int P, int M, int order, list stmts, gen_array_t annotations_s)
int	BDSC (sequence seq, int P, int M, int ordering)
int	DSC (sequence seq, int ordering)

Typedef Documentation

arc_label

typedef dg_arc_label arc_label

Instantiation of the dependence graph:

Definition at line 43 of file BDSC.c.

vertex_label

typedef dg_vertex_label vertex_label

Definition at line 44 of file BDSC.c.

Function Documentation

allocate_task_to_cluster()

void allocate_task_to_cluster	(	statement	ready_st,
		int	cl_p,
		int	order
	)

BDSC.c.

Parameters

ready_st	eady_st
cl_p	l_p
order	rder

Definition at line 100 of file BDSC.c.

                                                                      {
  annotation *an = gen_array_item(annotations, (int)statement_ordering(ready_st));
  list vertices = graph_vertices(kdg);
  an->scheduled = true;
  an->order_sched = order;
  an->cluster = cl_p;
  if(!bound_persistant_statement_to_cluster_p(stmt_to_cluster, statement_ordering(ready_st)))
    extend_persistant_statement_to_cluster(stmt_to_cluster, statement_ordering(ready_st), cl_p);
  else
    update_persistant_statement_to_cluster(stmt_to_cluster, statement_ordering(ready_st), cl_p);
  //delete ready_st from successors(tasks(cl_p))
  FOREACH(VERTEX, pre, vertices) {
    statement parent = vertex_to_statement(pre);
    annotation *anp = gen_array_item(annotations, (int)statement_ordering(parent));
    if(anp->cluster == cl_p)
      { 
        FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
          vertex v = successor_vertex(su);
          statement child = vertex_to_statement(v);
          if(statement_equal_p(child, ready_st)){
            double *ec = (double *)malloc(sizeof(double));
            *ec = 0;
            gen_array_addto(anp->edge_cost,(int)statement_ordering(ready_st), ec);
            gen_array_addto(annotations, (int)statement_ordering(parent), anp); 
          }
        }
      }
  }
 
  cluster *cl = gen_array_item(clusters, cl_p);
  double time = cl->time;
  double time1 = (time > an->tlevel) ? (time + an->task_time) : (an->tlevel + an->task_time);
  cl->time = time1;
  if(gen_length(vertex_successors(statement_to_vertex(ready_st,kdg)))> 0){
    list l_data = RegionsMustUnion(regions_dup(an->data), regions_dup(cl->data), r_w_combinable_p);
    cl->data = l_data;
  }
  gen_array_addto(clusters, cl_p, cl); 
  update_priority_values(ready_st);
  return;
}

References annotations, bound_persistant_statement_to_cluster_p(), annotation::cluster, clusters, annotation::data, cluster::data, annotation::edge_cost, extend_persistant_statement_to_cluster(), FOREACH, gen_array_addto(), gen_array_item(), gen_length(), graph_vertices, kdg, malloc(), annotation::order_sched, r_w_combinable_p(), regions_dup(), RegionsMustUnion(), annotation::scheduled, statement_equal_p(), statement_ordering, statement_to_vertex(), stmt_to_cluster, SUCCESSOR, successor_vertex, annotation::task_time, cluster::time, annotation::tlevel, update_persistant_statement_to_cluster(), update_priority_values(), VERTEX, vertex_successors, and vertex_to_statement().

Referenced by BDSC(), DSC(), DSRW(), find_cluster(), hierarchical_schedule(), and zeroing_multiple_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

BDSC()

int BDSC	(	sequence	seq,
		int	P,
		int	M,
		int	ordering
	)

canf instruction should be scheduled in the master cluster (by convention 0)

f(get_bool_property("BDSC_DISTRIBUTED_MEMORY")) zeroing_p = zeroing_multiple_edges(ready_task, order,M); function Not validated else

Parameters

seq	eq
ordering	rdering

Definition at line 535 of file BDSC.c.

                                                   {
  if(P <= 0)
    return 0;
  int nbclusters = 0;
  int order = 0, cl_p = -1;
  list unscheduled_tasks = NIL;
  list ready_tasks = NIL, unready_tasks = NIL;
  list stmts = sequence_statements(seq);
  statement ready_task = statement_undefined, unready_task = statement_undefined;
  gen_array_t annotations_s = schedule_failsafe();
  bool other_rules_p = false, scanf_p = false; 
  initialization_clusters(false);
  top_level(kdg, annotations);
  bottom_level(kdg, annotations);
  priorities(annotations);
  FOREACH(statement, st, stmts){
    if(!declaration_statement_p(st)) {
      unscheduled_tasks = CONS(STATEMENT, st, unscheduled_tasks);
      if(ready_node(st))
        ready_tasks = CONS(STATEMENT, st, ready_tasks);
      else
        unready_tasks = CONS(STATEMENT, st, unready_tasks);
    }
  }
  while(gen_length(unscheduled_tasks) > 0 ){
    ready_task = select_task_with_highest_priority(ready_tasks, statement_undefined);
    unready_task = select_task_with_highest_priority(unready_tasks, ready_task);
    other_rules_p = false, scanf_p = false; 
    if(statement_call_p(ready_task)){
      entity f = call_function(statement_call(ready_task));
      if(ENTITY_SCANF_P(f) || ENTITY_FSCANF_P(f) || ENTITY_SSCANF_P(f) 
         || ENTITY_ISOC99_FSCANF_P(f)|| ENTITY_ISOC99_SSCANF_P(f) || ENTITY_ISOC99_SCANF_P(f)) 
        scanf_p = true;
    }
    if(scanf_p){
      /*scanf instruction should be scheduled in the master cluster
        (by convention 0)*/
    allocate_task_to_cluster(ready_task, 0, order);
      if(nbclusters == 0) 
        nbclusters ++;
    }
    else{
      if(statement_undefined_p(unready_task)){
        cl_p = -1;
        statement min_pred = ready_task;
        bool zeroing_p = true;
        /*if(get_bool_property("BDSC_DISTRIBUTED_MEMORY")) 
          zeroing_p = zeroing_multiple_edges(ready_task, order,M);
          //function Not validated
          else*/
        {
          min_start_time min_pred_s =  tlevel_decrease(ready_task,M);
          min_pred =  min_pred_s.min_tau; 
          if(min_pred != statement_undefined)
            {
              annotation *anp = gen_array_item(annotations, (int)statement_ordering(min_pred));
              cl_p = anp->cluster;
              allocate_task_to_cluster(ready_task,cl_p, order);
            }
        }
        if(min_pred == statement_undefined || !zeroing_p)
          other_rules_p = true;
      }
      else {
        other_rules_p = DSRW(ready_task, unready_task,order,M);
      }
      if(other_rules_p)
        nbclusters = find_cluster(ready_task, nbclusters, P, M, order, stmts, annotations_s);
      if(nbclusters == -1)//not enough memorry
        return -1;
    }
    gen_remove_once(&unscheduled_tasks, ready_task);
    FOREACH(statement, st, unready_tasks){
      if(ready_node(st))
        gen_remove_once(&unready_tasks, st);
    }
    ready_tasks = NIL; 
    FOREACH(statement, st, unscheduled_tasks) {
      if(ready_node(st))
        ready_tasks = CONS(STATEMENT, st, ready_tasks);
    }
    order ++;
  }
  gen_array_free(annotations_s);
  update_parallel_task(ordering, nbclusters);
  return nbclusters;
}

References allocate_task_to_cluster(), annotations, bottom_level(), call_function, annotation::cluster, CONS, declaration_statement_p(), DSRW(), ENTITY_FSCANF_P, ENTITY_ISOC99_FSCANF_P, ENTITY_ISOC99_SCANF_P, ENTITY_ISOC99_SSCANF_P, ENTITY_SCANF_P, ENTITY_SSCANF_P, f(), find_cluster(), FOREACH, gen_array_free(), gen_array_item(), gen_length(), gen_remove_once(), initialization_clusters(), kdg, min_start_time::min_tau, NIL, priorities(), ready_node(), schedule_failsafe(), select_task_with_highest_priority(), sequence_statements, STATEMENT, statement_call(), statement_call_p(), statement_ordering, statement_undefined, statement_undefined_p, tlevel_decrease(), top_level(), and update_parallel_task().

Referenced by hierarchical_schedule().

Here is the call graph for this function:

Here is the caller graph for this function:

cancel_schedule()

static void cancel_schedule ( gen_array_t  annotations_s, list  stmts  )

static

Definition at line 471 of file BDSC.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 find_cluster().

Here is the call graph for this function:

Here is the caller graph for this function:

DSC()

int DSC	(	sequence	seq,
		int	ordering
	)

Parameters

seq	eq
ordering	rdering

Definition at line 623 of file BDSC.c.

                                    {
  int M = -1;
  int nbclusters = 0;
  int order = 0, cl_p = -1;
  list unscheduled_tasks = NIL;
  list ready_tasks = NIL, unready_tasks = NIL;
  list stmts = sequence_statements(seq);
  statement ready_task = statement_undefined, unready_task = statement_undefined;
  gen_array_t annotations_s = schedule_failsafe();
  bool other_rules_p = false; 
  top_level(kdg, annotations);
  bottom_level(kdg, annotations);
  priorities(annotations);
  FOREACH(statement, st, stmts){
    unscheduled_tasks = CONS(STATEMENT, st, unscheduled_tasks);
    if(ready_node(st))
      ready_tasks = CONS(STATEMENT, st, ready_tasks);
    else
      unready_tasks = CONS(STATEMENT, st, unready_tasks);
  }
  while(gen_length(unscheduled_tasks) > 0 ){
    ready_task = select_task_with_highest_priority(ready_tasks, statement_undefined);
    unready_task = select_task_with_highest_priority(unready_tasks, ready_task);
    other_rules_p = false; 
    if(statement_undefined_p(unready_task)){
      cl_p = -1;
      statement min_pred = ready_task;
      bool zeroing_p = true;
      if(get_bool_property("BDSC_DISTRIBUTED_MEMORY")) 
        zeroing_p = zeroing_multiple_edges(ready_task, order,M);
      else
        {
          min_start_time min_pred_s =  tlevel_decrease(ready_task,M);
          min_pred =  min_pred_s.min_tau; 
          if(min_pred != statement_undefined)
            {
              annotation *anp = gen_array_item(annotations, (int)statement_ordering(min_pred));
              cl_p = anp->cluster;
                allocate_task_to_cluster(ready_task,cl_p, order);
            }
        }
      if(min_pred == statement_undefined || !zeroing_p)
        other_rules_p = true;
    }
    else {
      other_rules_p = DSRW(ready_task, unready_task,order,M);
    }
    if(other_rules_p){
      cluster *cl_s = (cluster *)malloc(sizeof(cluster));
      cl_s->time = 0;
      cl_s->data = NIL;
      int i = nbclusters++;
      gen_array_addto(clusters, i, cl_s);
      allocate_task_to_cluster(ready_task, i, order);
    }
    gen_remove_once(&unscheduled_tasks, ready_task);
    FOREACH(statement, st, unready_tasks){
      if(ready_node(st))
        gen_remove_once(&unready_tasks, st);
    }
    ready_tasks = NIL; 
    FOREACH(statement, st, unscheduled_tasks) {
      if(ready_node(st))
        ready_tasks = CONS(STATEMENT, st, ready_tasks);
    }
    order ++;
  }
  gen_array_free(annotations_s);
  update_parallel_task(ordering, nbclusters);
  return nbclusters;
}

References allocate_task_to_cluster(), annotations, bottom_level(), annotation::cluster, clusters, CONS, cluster::data, DSRW(), FOREACH, gen_array_addto(), gen_array_free(), gen_array_item(), gen_length(), gen_remove_once(), get_bool_property(), kdg, malloc(), min_start_time::min_tau, NIL, priorities(), ready_node(), schedule_failsafe(), select_task_with_highest_priority(), sequence_statements, STATEMENT, statement_ordering, statement_undefined, statement_undefined_p, cluster::time, tlevel_decrease(), top_level(), update_parallel_task(), and zeroing_multiple_edges().

Referenced by hierarchical_schedule().

Here is the call graph for this function:

Here is the caller graph for this function:

DSRW()

static bool DSRW ( statement  ready_st, statement  unready_st, int  order, int  M  )

static

Definition at line 407 of file BDSC.c.

                                                                            {
  int cl_p; bool DSRW_p = false;
  min_start_time r_min_pred_s = tlevel_decrease(ready_st, M);
  statement r_min_pred = r_min_pred_s.min_tau;
  if(r_min_pred != statement_undefined)
    {
      min_start_time u_min_pred_s = tlevel_decrease(unready_st,M);
      double ptlevel_before = u_min_pred_s.min_tlevel; 
      annotation *anp = gen_array_item(annotations, (int)statement_ordering(r_min_pred));
      cl_p = anp->cluster;
      u_min_pred_s = tlevel_decrease(unready_st,M);
      double ptlevel_after = u_min_pred_s.min_tlevel; 
      if(ptlevel_after > ptlevel_before){
        DSRW_p = true;
      }
      else
        allocate_task_to_cluster(ready_st,cl_p, order);
    }
  if ((r_min_pred == statement_undefined) || DSRW_p)    
    return true;
  else 
    return false;
}

References allocate_task_to_cluster(), annotations, annotation::cluster, gen_array_item(), min_start_time::min_tau, min_start_time::min_tlevel, statement_ordering, statement_undefined, and tlevel_decrease().

Referenced by BDSC(), and DSC().

Here is the call graph for this function:

Here is the caller graph for this function:

end_idle_clusters()

static int end_idle_clusters ( statement  ready_st, int  nbclusters  )

static

pply the second priority : load balancing : length_cluster(c_i) < tlevel(ready_st) and forall node n_y in c_i scheduled(successors(n_y)) = true or successors(n_y) \subset successors(ready_st)

Definition at line 328 of file BDSC.c.

                                                                {
  list vertices = graph_vertices(kdg);
  annotation *an = gen_array_item(annotations, (int)statement_ordering(ready_st));
  double min_time = an->tlevel, time_cluster;
  bool found_p;
  int min_cluster = -1;
  vertex ready_vertex = statement_to_vertex(ready_st, kdg);
  for(int cl = 0; cl < nbclusters; cl++){
    cluster *cl_s =  gen_array_item(clusters, cl); ;
    time_cluster = cl_s->time;
    if(time_cluster <= min_time)
      {
        found_p = true;
        FOREACH(VERTEX, pre, vertices) {
          statement parent = vertex_to_statement(pre);
          annotation *anp = gen_array_item(annotations, (int)statement_ordering(parent));
          if(anp->cluster == cl){              
            FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
              vertex v = successor_vertex(su);
              statement child = vertex_to_statement(v);
              annotation *anc = gen_array_item(annotations, (int)statement_ordering(child));
              if(!anc->scheduled)
                {
                  FOREACH(SUCCESSOR, su_r, vertex_successors(ready_vertex)) {
                    if(!statement_equal_p(vertex_to_statement(successor_vertex(su_r)), child)) 
                      {
                        found_p = false;
                        break;
                      }
                  }
                }
            }
          }
        }
        if(found_p)
          {
            min_time = min_time > time_cluster ? time_cluster : min_time;
            min_cluster = (min_time > time_cluster || min_cluster == -1) ? cl : min_cluster;
          }
      }
  }
  return min_cluster;
}

References annotations, annotation::cluster, clusters, FOREACH, gen_array_item(), graph_vertices, kdg, annotation::scheduled, statement_equal_p(), statement_ordering, statement_to_vertex(), SUCCESSOR, successor_vertex, cluster::time, annotation::tlevel, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by find_cluster().

Here is the call graph for this function:

Here is the caller graph for this function:

find_cluster()

static int find_cluster ( statement  ready_task, int  nbclusters, int  P, int  M, int  order, list  stmts, gen_array_t  annotations_s  )

static

Definition at line 511 of file BDSC.c.

{
  //second priority: load balancing
  int cl_p = end_idle_clusters(ready_task, nbclusters);
  if(cl_p == -1 ||  (MEMORY_SIZE != -1 && !MCW(ready_task,cl_p,M)))
    { //third priority: PCW
      if(nbclusters < P && (MEMORY_SIZE == -1 || MCW(ready_task,nbclusters,M)))
        cl_p = nbclusters ++;
      else
        {
          cl_p = min_start_time_cluster(nbclusters);
          if(MEMORY_SIZE != -1 && !MCW(ready_task,cl_p,M))
            {
              cancel_schedule(annotations_s, stmts);
              fprintf (stderr, "OUUPS, Not Enough Memory but let's try the hierarchical enclosed tasks\n");
              return -1;
            }
        }
    }
  allocate_task_to_cluster(ready_task,cl_p, order);
  return nbclusters;
}

References allocate_task_to_cluster(), cancel_schedule(), end_idle_clusters(), fprintf(), MCW(), MEMORY_SIZE, and min_start_time_cluster().

Referenced by BDSC().

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 487 of file BDSC.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 BDSC().

Here is the call graph for this function:

Here is the caller graph for this function:

max_start_time_cluster()

static double max_start_time_cluster ( int  nbclusters )

static

sed to compute the parallel task time of a task

Definition at line 393 of file BDSC.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 == -1)
       {
         max = time;
       }
    }
  return max;
}

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

Referenced by update_parallel_task().

Here is the call graph for this function:

Here is the caller graph for this function:

MCW()

static bool MCW ( statement  ready_st, int  cl, int  M  )

static

Definition at line 163 of file BDSC.c.

{
  if(gen_length(vertex_successors(statement_to_vertex(ready_st,kdg)))==0)
    return true;
  if(cl != -1){
    annotation *an = gen_array_item(annotations, (int)statement_ordering(ready_st));
    cluster *cl_s = gen_array_item(clusters, cl);
    list l_data = RegionsMustUnion(regions_dup(an->data), regions_dup(cl_s->data), w_w_combinable_p);
    return (size_of_regions(l_data) < M);
  }
  return false;
}

References annotations, clusters, annotation::data, cluster::data, gen_array_item(), gen_length(), kdg, regions_dup(), RegionsMustUnion(), size_of_regions(), statement_ordering, statement_to_vertex(), vertex_successors, and w_w_combinable_p().

Referenced by find_cluster(), tlevel_decrease(), and zeroing_multiple_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

min_start_time_cluster()

static int min_start_time_cluster ( int  nbclusters )

static

pply the third priority if bounded number of processors is exceeded start-time(ready_st) = min(length_cluster(c_i)) tlevel(ready_st) can be increased.

Definition at line 376 of file BDSC.c.

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

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

Referenced by find_cluster().

Here is the call graph for this function:

Here is the caller graph for this function:

move_task_to_cluster()

static void move_task_to_cluster ( statement  ready_st, int  cl_p  )

static

Definition at line 142 of file BDSC.c.

                                                              {
  annotation *an = gen_array_item(annotations, (int)statement_ordering(ready_st));
  //int cl_i = an->cluster;
  cluster *cl = gen_array_item(clusters, an->cluster);
  double time = cl->time;
  cl->time = time -  an->task_time;
  gen_array_addto(clusters, an->cluster, cl); 
  an->cluster = cl_p;
  extend_persistant_statement_to_cluster(stmt_to_cluster, statement_ordering(ready_st), cl_p);
  cl = gen_array_item(clusters, cl_p);
  time = cl->time;
  cl->time = time > an->tlevel + an->task_time? time : an->tlevel + an->task_time;
  if(gen_length(vertex_successors(statement_to_vertex(ready_st,kdg)))> 0){
    list l_data = RegionsMustUnion(regions_dup(an->data), regions_dup(cl->data), r_w_combinable_p);
    cl->data = l_data;
  }
  gen_array_addto(clusters, cl_p, cl); 
  update_priority_values(ready_st);
  return;
}

References annotations, annotation::cluster, clusters, annotation::data, cluster::data, extend_persistant_statement_to_cluster(), gen_array_addto(), gen_array_item(), gen_length(), kdg, r_w_combinable_p(), regions_dup(), RegionsMustUnion(), statement_ordering, statement_to_vertex(), stmt_to_cluster, annotation::task_time, cluster::time, annotation::tlevel, update_priority_values(), and vertex_successors.

Referenced by zeroing_multiple_edges().

Here is the call graph for this function:

Here is the caller graph for this function:

ready_node()

static bool ready_node ( statement  st )

static

Definition at line 59 of file BDSC.c.

                                    {
  bool ready_p = true;
  list vertices = graph_vertices(kdg);
  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, st))  {
        annotation *anp = gen_array_item(annotations, (int)statement_ordering(parent));
        bool sc_p = anp->scheduled;
        if(!sc_p){
          ready_p = false;
          break;
        }
      }
    }
  }
  return ready_p;
}

References annotations, FOREACH, gen_array_item(), graph_vertices, kdg, annotation::scheduled, statement_equal_p(), statement_ordering, SUCCESSOR, successor_vertex, 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:

schedule_failsafe()

static gen_array_t schedule_failsafe ( )

static

Definition at line 451 of file BDSC.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 BDSC(), and DSC().

Here is the call graph for this function:

Here is the caller graph for this function:

select_task_with_highest_priority()

static statement select_task_with_highest_priority ( list  tasks, statement  ready  )

static

Definition at line 431 of file BDSC.c.

                                                                               {
  double max;
  statement highest_task = statement_undefined;
  if(!statement_undefined_p(ready)){
    annotation *item = gen_array_item(annotations, statement_ordering(ready));
    max = item->prio;
  }
  else
    max = -1;
  FOREACH(statement, st, tasks) {
    annotation *item = gen_array_item(annotations, statement_ordering(st));
    if(item->prio > max)//just for unexamined nodes
      {
        max = item->prio;
        highest_task = st;
      }
  }
  return highest_task;
}

References annotations, FOREACH, gen_array_item(), max, annotation::prio, statement_ordering, statement_undefined, and statement_undefined_p.

Referenced by BDSC(), and DSC().

Here is the call graph for this function:

Here is the caller graph for this function:

tlevel_decrease()

static min_start_time tlevel_decrease ( statement  ready_st, int  M  )

static

dge_cost(parent1,ready_st);

Definition at line 175 of file BDSC.c.

                                                                {
  list vertices = graph_vertices(kdg);
  annotation *an = gen_array_item(annotations, (int)statement_ordering(ready_st));
  min_start_time min_pred; 
  double  time;
  statement min_predecessor = statement_undefined;
  double  min_tlevel = an->tlevel; 
  FOREACH(VERTEX, pre, vertices) {
    statement parent = vertex_to_statement(pre);
    annotation *anp = gen_array_item(annotations, (int)statement_ordering(parent));
    if(anp->scheduled && (MEMORY_SIZE == -1 || MCW(ready_st,anp->cluster,M)))
      {
        FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
          vertex s = successor_vertex(su);
          statement child = vertex_to_statement(s);
          if(statement_equal_p(child, ready_st)) //pre is predecessor of ready_st
            {
              cluster *cl_s =  gen_array_item(clusters, anp->cluster);
              double new_tlevel = cl_s->time;
              FOREACH(VERTEX, pre1, vertices) {// all predecessors minus this parent
                statement parent1 = vertex_to_statement(pre1);
                annotation *anp1 = gen_array_item(annotations, (int)statement_ordering(parent1));
                if(anp1->scheduled){
                  FOREACH(SUCCESSOR, su1, (vertex_successors(pre1))) {
                    vertex s1 = successor_vertex(su1);
                    statement child1 = vertex_to_statement(s1);
                    if(statement_equal_p(child1, ready_st))//pre1 is predecessor of ready_st
                      {
                        if (!statement_equal_p(parent, parent1)){
                          double edge_c = *(double *)(gen_array_item(anp1->edge_cost,statement_ordering(ready_st)));
                          time = anp1->tlevel + anp1->task_time + edge_c /*edge_cost(parent1,ready_st);*/  ;
                          new_tlevel = new_tlevel > time ? new_tlevel : time;
                        }
                      }
                    }
                }
              }
              if(new_tlevel <= min_tlevel){
                min_tlevel = new_tlevel;
                min_predecessor = parent;
              }
            }
        }
      }
  }
  min_pred.min_tlevel = min_tlevel;
  min_pred.min_tau = min_predecessor;
  return min_pred;
}

References annotations, annotation::cluster, clusters, annotation::edge_cost, FOREACH, gen_array_item(), graph_vertices, kdg, MCW(), MEMORY_SIZE, min_start_time::min_tau, min_start_time::min_tlevel, s1, annotation::scheduled, statement_equal_p(), statement_ordering, statement_undefined, SUCCESSOR, successor_vertex, annotation::task_time, cluster::time, annotation::tlevel, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by BDSC(), DSC(), and DSRW().

Here is the call graph for this function:

Here is the caller graph for this function:

update_parallel_task()

static void update_parallel_task ( int  ordering, int  nbclusters  )

static

Definition at line 503 of file BDSC.c.

{
  annotation *item = gen_array_item(annotations,ordering);
  item->data = NIL;
  item->task_time = max_start_time_cluster(nbclusters);
  return;
}

References annotations, annotation::data, gen_array_item(), max_start_time_cluster(), NIL, and annotation::task_time.

Referenced by BDSC(), and DSC().

Here is the call graph for this function:

Here is the caller graph for this function:

update_priority_values()

static void update_priority_values ( statement  ready_st )

static

Definition at line 81 of file BDSC.c.

{
  //update the priorities of ready_st successors
  FOREACH(SUCCESSOR, su, (vertex_successors(statement_to_vertex(ready_st, kdg)))) {
    vertex s = successor_vertex(su);
    statement child = vertex_to_statement(s);
    annotation *anc = gen_array_item(annotations, (int)statement_ordering(child));
    anc->tlevel = -1;
  }
  FOREACH(SUCCESSOR, su, (vertex_successors(statement_to_vertex(ready_st, kdg)))) {
    vertex s = successor_vertex(su);
    statement child = vertex_to_statement(s);
    annotation *anc = gen_array_item(annotations, (int)statement_ordering(child));
    t_level(s, kdg, annotations);
    anc->prio = anc->tlevel + anc->blevel;
  }
  return; 
}

References annotations, annotation::blevel, FOREACH, gen_array_item(), kdg, annotation::prio, statement_ordering, statement_to_vertex(), SUCCESSOR, successor_vertex, t_level(), annotation::tlevel, vertex_successors, and vertex_to_statement().

Referenced by allocate_task_to_cluster(), and move_task_to_cluster().

Here is the call graph for this function:

Here is the caller graph for this function:

zeroing_multiple_edges()

static bool zeroing_multiple_edges ( statement  ready_st, int  order, int  M  )

static

Definition at line 225 of file BDSC.c.

{
  list vertices = graph_vertices(kdg);
  annotation *an = gen_array_item(annotations, (int)statement_ordering(ready_st));
  double time;
  int i, j, min_cluster = -1;
  bool zeroing_p = false;
  typedef struct {
    statement predecessor;
    double time;
  }zeroing;
  zeroing *zeroing_can; 
  gen_array_t sorted_predecessors = gen_array_make(0);
  double min_tlevel = an->tlevel; 
  FOREACH(VERTEX, pre, vertices) {
    statement parent = vertex_to_statement(pre);
    annotation *anp = gen_array_item(annotations, (int)statement_ordering(parent));
    if(anp->cluster != -1)
      {
        FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
          vertex s = successor_vertex(su);
          statement child = vertex_to_statement(s);
          if(statement_equal_p(child, ready_st)) //pre is predecessor of ready_st
            {
              double edge_c = *(double *)(gen_array_item(anp->edge_cost,statement_ordering(ready_st)));
              cluster  *cl = gen_array_item(clusters, anp->cluster);
              double new_tlevel = cl->time;
              time = anp->tlevel + anp->task_time + edge_c; 
              new_tlevel = new_tlevel > time ? new_tlevel : time;
              if(new_tlevel <= min_tlevel + edge_c){
                int array_size = gen_array_nitems(sorted_predecessors);
                zeroing *zer_new = (zeroing *)malloc(sizeof(zeroing));
                zer_new->predecessor = parent;
                zer_new->time = new_tlevel;
                i=0;
                if(array_size > 0){
                  zeroing_can = gen_array_item(sorted_predecessors, i);
                  while(i< array_size)
                    {
                      zeroing_can = gen_array_item(sorted_predecessors, i);
                      if(new_tlevel <= zeroing_can->time)
                        break;
                      i++;
                    }
                  if(new_tlevel <= zeroing_can->time) //shift
                    {
                      zeroing *zer = gen_array_item(sorted_predecessors, i+1);
                      gen_array_addto(sorted_predecessors, i+1, zeroing_can);
                      gen_array_addto(sorted_predecessors, i, zer_new);
                      for(j = i+1; j< array_size+1; j++)
                        {
                          zeroing_can = gen_array_item(sorted_predecessors, j+1);
                          gen_array_addto(sorted_predecessors, j+1, zer);
                          zer = zeroing_can;
                        }
                    }
                }
                if(i == array_size)
                  gen_array_addto(sorted_predecessors, i, zer_new);
              }
            }
        }
      }
  }
  i = 0;
  while(i<(int)gen_array_nitems(sorted_predecessors)){
    zeroing *zer= gen_array_item(sorted_predecessors, i);
    statement min_predecessor = copy_statement(zer->predecessor); 
    annotation *anp = gen_array_item(annotations, (int)statement_ordering(min_predecessor));
    min_cluster = anp->cluster;
    if(MEMORY_SIZE == -1 || MCW(ready_st,min_cluster,M))
      {
        zeroing_p = true;
        allocate_task_to_cluster(ready_st, min_cluster,order);
        break;
      }
    i++;
  }
  i= i+1;
  double sum = 0;
  while(i<(int)gen_array_nitems(sorted_predecessors))
    {
      zeroing *zer= gen_array_item(sorted_predecessors, i);
      statement parent = zer->predecessor; 
      annotation *anp = gen_array_item(annotations, (int)statement_ordering(parent));
      double edge_c = *(double *)(gen_array_item(anp->edge_cost,statement_ordering(ready_st)));
      sum = sum + anp->task_time;
      if(sum <= edge_c && (int)(gen_length(vertex_successors(statement_to_vertex(parent,kdg))) == 1)
         && (MEMORY_SIZE == -1 || MCW(parent,min_cluster,M)))
        {
          move_task_to_cluster(parent,min_cluster);
        }
      else
        break;
      i++;
    }
  gen_array_free( sorted_predecessors);
  return zeroing_p;
}

References allocate_task_to_cluster(), annotations, array_size(), annotation::cluster, clusters, copy_statement(), annotation::edge_cost, FOREACH, gen_array_addto(), gen_array_free(), gen_array_item(), gen_array_make(), gen_array_nitems(), gen_length(), graph_vertices, kdg, malloc(), MCW(), MEMORY_SIZE, move_task_to_cluster(), statement_equal_p(), statement_ordering, statement_to_vertex(), SUCCESSOR, successor_vertex, sum(), annotation::task_time, cluster::time, annotation::tlevel, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by DSC().

Here is the call graph for this function:

Here is the caller graph for this function: