implemented binary search

7 files changed, 213 insertions, 13 deletions

diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.cpp
index 7899c8e1f3d..58f7536d201 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.cpp
@@ -14,6 +14,26 @@
 #include <sstream>
 #include "Algorithms.h"
 
+PROCESSOR_LIST create_processors (unsigned long count)
+{
+  PROCESSOR_LIST procs;
+
+  for (unsigned long i = 1; i <= count; ++i)
+    {
+      std::stringstream ss;
+      ss << "P";
+      if (i < 10)
+        ss << "00";
+      else if (i < 100)
+        ss << "0";
+
+      ss << i;
+      procs.push_back (ss.str ());
+    }
+
+  return procs;
+}
+
 FTRMFF_Algorithm::~FTRMFF_Algorithm ()
 {
 }
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.h
index 606c8669b51..ca326eb647c 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.h
@@ -78,6 +78,8 @@ typedef std::string Processor;
 typedef std::list <Processor> PROCESSOR_LIST;
 typedef unsigned long Priority;
 
+PROCESSOR_LIST create_processors (unsigned long count);
+
 struct TaskPlacement
 {
   Processor processor;
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
index cefc534b726..2d40af19bbf 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
@@ -96,6 +96,30 @@ project (bestfit_ftrmff) {
   }
 }
 
+project (binary_ftrmff) {
+
+  exename = bsftrmff
+  exeout = ../bin
+
+  macros += DO_DEBUG
+
+  Source_Files {
+    Algorithms.cpp
+    Schedule.cpp
+    CTT_Basic.cpp
+    CTT_Enhanced.cpp
+    Task_Scheduler.cpp
+    Utilization_Ranking.cpp
+    OptimizedWCRT.cpp
+    RankedWCRT.cpp
+    Simple_Ranking.cpp
+    FTRMFF_Bestfit.cpp
+    FTRMFF_Binary_Search.cpp
+    FTRMFF_Basic.cpp
+    binary_ftrmff.cpp
+  }
+}
+
 project (schedulability_check) : acelib {
 
   exename = scheck
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
index 81e61148904..98cca0f995e 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
@@ -29,7 +29,7 @@ class FTRMFF_Bestfit_Algorithm :
 {
 public:
   FTRMFF_Bestfit_Algorithm (const PROCESSOR_LIST & processors,
-                           unsigned int consistency_level);
+                            unsigned int consistency_level);
 
   virtual ~FTRMFF_Bestfit_Algorithm ();
 
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp
index 74741524c66..e4b7df6eac7 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp
@@ -11,9 +11,10 @@
 //=============================================================================
 
 #include "FTRMFF_Binary_Search.h"
-#include "FTRMFF_Primary.h"
 #include "FTRMFF_Basic.h"
+#include "FTRMFF_Bestfit.h"
 #include "CTT_Enhanced.h"
+#include "CTT_Basic.h"
 
 FTRMFF_Binary_Search::~FTRMFF_Binary_Search ()
 {
@@ -29,6 +30,8 @@ FTRMFF_Binary_Search::operator () (const FTRMFF_Input & input)
   output.schedule = algorithm (input.tasks);
   output.unscheduled_tasks = algorithm.get_unschedulable ();
 
+  DBG_OUT (algorithm.schedule ());
+
   return output;
 }
 
@@ -36,6 +39,7 @@ FTRMFF_Binary_Search_Algorithm::FTRMFF_Binary_Search_Algorithm (
   const PROCESSOR_LIST & processors,
   unsigned int consistency_level)
   : processors_ (processors),
+    schedule_ (create_schedule (processors)),
     consistency_level_ (consistency_level)
 {
 }
@@ -47,6 +51,7 @@ FTRMFF_Binary_Search_Algorithm::~FTRMFF_Binary_Search_Algorithm ()
 SCHEDULING_MAP
 FTRMFF_Binary_Search_Algorithm::operator () (const TASK_LIST & tasks)
 {
+#if 0
   // step one, only schedule primaries to get lower bound
   FTRMFF_Primary_Algorithm primary_ftrmff (processors_);
 
@@ -54,8 +59,7 @@ FTRMFF_Binary_Search_Algorithm::operator () (const TASK_LIST & tasks)
 
   unsigned long minimum = 
     processor_usage (primary_ftrmff.schedule ());
-
-  std::cout << minimum << " ";
+#endif
 
   // step two, schedule replicas with only state synchronization times
   CTT_Enhanced ctt_enhanced;
@@ -68,8 +72,6 @@ FTRMFF_Binary_Search_Algorithm::operator () (const TASK_LIST & tasks)
   unsigned long lower_bound = 
     processor_usage (only_ss_ftrmff.schedule ());
 
-  std::cout << lower_bound << " ";
-
   // step three, schedule all replicas as active
   CTT_Basic ctt_basic;
   FTRMFF_Basic_Algorithm active_ftrmff (processors_,
@@ -81,9 +83,61 @@ FTRMFF_Binary_Search_Algorithm::operator () (const TASK_LIST & tasks)
   unsigned long upper_bound = 
     processor_usage (active_ftrmff.schedule ());
 
-  std::cout << upper_bound << std::endl;
-
-  return SCHEDULING_MAP ();
+  unsigned long min = lower_bound;
+  unsigned long max = upper_bound;
+  unsigned long processors = upper_bound;
+
+  while (min < max)
+    {
+      TRACE ("Binary Search: max = " << max << " min = " << min);
+
+      // schedule with the average value between minimum and maximum
+      FTRMFF_Bestfit_Algorithm bestfit_ftrmff (
+        create_processors (min + ((max - min)/2)),
+        consistency_level_);
+     
+      bestfit_ftrmff (tasks);
+
+      // determine number of used processors
+      processors = processor_usage (bestfit_ftrmff.schedule ());
+
+      // if successful schedule
+      if (bestfit_ftrmff.get_unschedulable ().empty ())
+        {
+          // store number of processors as new max
+          max = processors;
+          schedule_ = bestfit_ftrmff.schedule ();
+        }
+      else // not schedulable
+        {
+          // don't look for solutions with smaller numbers of
+          // processors
+          min = processors + 1;
+        }
+    }
+
+  if ((min < upper_bound) && (processor_usage (schedule_) > 0))
+    {
+      return transform_schedule (schedule_);
+    }
+  else
+    {
+      // in failure case try maximum number of processors and then
+      // give up.
+      FTRMFF_Bestfit_Algorithm bestfit_ftrmff (
+        create_processors (max),
+        consistency_level_);
+      
+      SCHEDULING_MAP result = bestfit_ftrmff (tasks);
+
+      unschedulable_ = bestfit_ftrmff.get_unschedulable ();
+
+      schedule_ = bestfit_ftrmff.schedule ();
+
+      return result;
+    }
+
+  return transform_schedule (schedule_);
 }
 
 SCHEDULE_PROGRESS_LIST
@@ -91,3 +145,9 @@ FTRMFF_Binary_Search_Algorithm::get_unschedulable ()
 {
   return unschedulable_;
 }
+
+const SCHEDULE & 
+FTRMFF_Binary_Search_Algorithm::schedule () const
+{
+  return schedule_;
+}
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.h
index 9e91eae404a..7f53d537949 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.h
@@ -10,8 +10,8 @@
  */
 //=============================================================================
 
-#ifndef FTRMFF_BESTFIT_ALGORITHM_H_
-#define FTRMFF_BESTFIT_ALGORITHM_H_
+#ifndef FTRMFF_BINARY_SEARCH_ALGORITHM_H_
+#define FTRMFF_BINARY_SEARCH_ALGORITHM_H_
 
 #include "Schedule.h"
 
@@ -29,7 +29,7 @@ class FTRMFF_Binary_Search_Algorithm :
 {
 public:
   FTRMFF_Binary_Search_Algorithm (const PROCESSOR_LIST & processors,
-                           unsigned int consistency_level);
+                                  unsigned int consistency_level);
 
   virtual ~FTRMFF_Binary_Search_Algorithm ();
 
@@ -37,10 +37,13 @@ public:
 
   SCHEDULE_PROGRESS_LIST get_unschedulable ();
 
+  const SCHEDULE & schedule () const;
+
 private:
   const PROCESSOR_LIST & processors_;
+  SCHEDULE schedule_;
   SCHEDULE_PROGRESS_LIST unschedulable_;
   unsigned int consistency_level_;
 };
 
-#endif /* FTRMFF_BESTFIT_ALGORITHM_H_ */
+#endif /* FTRMFF_BINARY_SEARCH_ALGORITHM_H_ */
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_ftrmff.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_ftrmff.cpp
new file mode 100644
index 00000000000..eedcb55a449
--- /dev/null
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_ftrmff.cpp
@@ -0,0 +1,91 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    binary_ftrmff.cpp
+ *
+ *  $Id$
+ *
+ *  @author  Friedhelm Wolf (fwolf@dre.vanderbilt.edu)
+ */
+//=============================================================================
+
+#include <fstream>
+#include <sstream>
+#include <iostream>
+#include <ace/Get_Opt.h>
+#include "FTRMFF_Binary_Search.h"
+
+std::string filename = "test.sd"; // filename of task list input
+unsigned int m = 4; // number of processors
+unsigned int c = 2; // consitency level
+
+int ACE_TMAIN (int argc, ACE_TCHAR *argv[])
+{
+  if (argc > 1)
+    filename = argv[1];
+
+  if (argc > 2)
+    m = atoi (argv[2]);
+
+  if (argc > 3)
+    c = atoi (argv[3]);
+
+  TASK_LIST tasks;
+  PROCESSOR_LIST procs;
+  for (unsigned int i = 1; i <= m; ++i)
+    {
+      std::stringstream ss;
+      ss << "P";
+      if (i < 10)
+        ss << "00";
+      else if (i < 100)
+        ss << "0";
+      ss << i;
+      procs.push_back (ss.str ());
+    }
+
+  std::ifstream ifile;
+  ifile.open (filename.c_str ());
+
+  std::transform (
+    std::istream_iterator <std::string> (ifile),
+    std::istream_iterator <std::string> (),
+    std::inserter <TASK_LIST> (tasks,
+                               tasks.begin ()),
+    string_to_task ());
+  
+  ifile.close ();
+
+  FTRMFF_Binary_Search ftrmff;
+
+  FTRMFF_Input input;
+  input.tasks = tasks;
+  input.processors = procs;
+  input.backup_count = c;
+  FTRMFF_Output result = ftrmff (input);
+
+#if 0
+  for (SCHEDULING_MAP::iterator it = result.schedule.begin ();
+       it != result.schedule.end ();
+       ++it)
+    {
+      std::cout << it->first << " -> " 
+                << it->second.processor 
+                << " (" << it->second.priority << ")" 
+                << std::endl;
+    }
+#endif
+
+  if (result.unscheduled_tasks.size () > 0)
+    {
+      std::cout << "Could not schedule :"
+                << std::endl
+                << result.unscheduled_tasks
+                << std::endl;
+
+      return 1;
+    }
+
+  return 0;
+}