Text archives Help

---

Author: cgribble
Date: Wed Jul 19 17:39:48 2006
New Revision: 1148

Added:
   trunk/Engine/Control/DynPLTQueue.cc
Modified:
   trunk/Engine/Control/CMakeLists.txt
   trunk/Engine/Control/DynPLTQueue.h
   trunk/Engine/Control/DynPLTWorker.cc
   trunk/Model/Primitives/DynPLTGridSpheres.cc
   trunk/Model/Primitives/DynPLTGridSpheres.h
   trunk/scenes/dynplt.cc
Log:
scenes/dynplt.cc
  Added "-fifo" cmdln parameter to use FIFO (and not Priority) Queue for 
texture
    scheduling

Model/Primitives/DynPLTGridSpheres.cc
Model/Primitives/DynPLTGridSpheres.h
  Added accessor to set particle's requested flag to false
  Added calls to queue->updatePriority(...) for previously requested, but not 
yet
    valid textures

Engine/Control/DynPLTQueue.h
Engine/Control/DynPLTQueue.cc
Engine/Control/DynPLTWorker.cc
Engine/Control/CMakeLists.txt
  Added priority queue with several different (compile-time) heuristics for
    scheduling textures
  Works nicely for small datasets, but for large ones (e.g., jp8) there seems 
to
    be a lot of contention for the mutex (for updating priorities, I think); 
will
    require profiling to determine culprit for sure
  Changed DynPLTMessage constructor interface (in case we want to use the 
ray's
    t-value or some such in the priority computation)


Modified: trunk/Engine/Control/CMakeLists.txt
==============================================================================
--- trunk/Engine/Control/CMakeLists.txt (original)
+++ trunk/Engine/Control/CMakeLists.txt Wed Jul 19 17:39:48 2006
@@ -9,6 +9,7 @@
    SET(Manta_Control_SRCS
        ${Manta_Control_SRCS}
        Control/DynPLTQueue.h
+       Control/DynPLTQueue.cc
        Control/DynPLTWorker.h
        Control/DynPLTWorker.cc
    )

Added: trunk/Engine/Control/DynPLTQueue.cc
==============================================================================
--- (empty file)
+++ trunk/Engine/Control/DynPLTQueue.cc Wed Jul 19 17:39:48 2006
@@ -0,0 +1,228 @@
+
+#include <Engine/Control/DynPLTQueue.h>
+#include <Model/Primitives/DynPLTGridSpheres.h>
+
+#include <iostream>
+using std::cerr;
+
+using namespace Manta;
+
+DynPLTPriorityQ::DynPLTPriorityQ(int size) :
+  mutex("PriorityQ lock"), empty("PriorityQ empty condition"),
+  full("PriorityQ full condition"), nheap(0),
+  max_size(size)
+{
+  // Allocate dataspace
+  dataspace=new char[max_size*sizeof(DynPLTMessage)];
+  heap=reinterpret_cast<DynPLTMessage*>(dataspace);
+}
+
+DynPLTPriorityQ::~DynPLTPriorityQ(void)
+{
+  // Release all waiting threads
+  empty.conditionBroadcast();
+  full.conditionBroadcast();
+
+  // Free dataspace
+  delete [] dataspace;
+}
+
+bool DynPLTPriorityQ::tryReceive(DynPLTMessage& msg)
+{
+  mutex.lock();
+
+  // Return false if heap is empty
+  if (nheap==0) {
+    mutex.unlock();
+    return false;
+  }
+
+  // Pop top item from the heap
+  msg=pop();
+
+  mutex.unlock();
+
+  return true;
+}
+
+DynPLTMessage DynPLTPriorityQ::receive(void)
+{
+  mutex.lock();
+
+  // Block calling thread while heap is empty
+  while (nheap==0)
+    empty.wait(mutex);
+
+  // Pop top item from the heap
+  DynPLTMessage msg=pop();
+
+  mutex.unlock();
+
+  return msg;
+}
+
+bool DynPLTPriorityQ::trySend(const DynPLTMessage& msg)
+{
+  mutex.lock();
+
+  // Return false if heap is full
+  if (nheap==max_size) {
+    mutex.unlock();
+    return false;
+  }
+
+  push(msg);
+  mutex.unlock();
+
+  return true;
+}
+
+void DynPLTPriorityQ::send(const DynPLTMessage& msg)
+{
+  mutex.lock();
+
+  // Block calling thread while heap is full
+  while (nheap==max_size)
+    full.wait(mutex);
+
+  push(msg);
+  mutex.unlock();
+}
+
+void DynPLTPriorityQ::updatePriority(int particle, Real t)
+{
+  // NOTE:  I suspect that this code causes a lot of contention for the 
queue's
+  //        mutex, and is responsible for the huge slow down with large 
datasets;
+  //        maybe only update the priority after so many frames or something?
+  mutex.lock();
+
+  for (unsigned int i=0; i<nheap; ++i) {
+    if (heap[i].particle == particle) {
+      // Found particle, create new node with updated priority
+      DynPLTMessage msg(particle, t, heap[i].grid);
+
+      // Staring at old node's position in the heap, walk new node up the 
heap
+      // until its priority is less than its parent's
+      int parent=(i + 1)/2 - 1;
+      while (i && heap[parent].priority < msg.priority) {
+        heap[i]=heap[parent];
+        i=parent;
+        parent=(i + 1)/2 - 1;
+      }
+
+      // Insert message
+      heap[i]=msg;
+
+      break;
+    }
+  }
+
+  mutex.unlock();
+}
+
+void DynPLTPriorityQ::push(DynPLTMessage const& msg)
+{
+#if 0
+  // NOTE:  This code is supposed to implement a fixed size queue in which 
old
+  //        requests (i.e., low priority) are dropped and new ones added; it
+  //        sort of works, but I'm not sure it's bullet proof yet...
+  if (nheap<max_size) {
+    // Increment number of nodes in the heap
+    ++nheap;
+
+    // Walk node up the heap until its priority is less than its parent's
+    int i=nheap - 1;
+    int parent=(i + 1)/2 - 1;
+    while (i && heap[parent].priority < msg.priority) {
+      heap[i]=heap[parent];
+      i=parent;
+      parent=(i + 1)/2 - 1;
+    }
+
+    // Insert message
+    heap[i]=msg;
+  } else {
+    // Drop last node
+    DynPLTMessage last=heap[nheap-1];
+    DynPLTGridSpheres* grid=const_cast<DynPLTGridSpheres*>(last.grid);
+    grid->resetRequested(last.particle);
+
+    // Move old root to end, insert new node at root, and rebuild
+    heap[nheap-1]=heap[0];
+    heap[0]=msg;
+    heapify(0, nheap);
+  }
+#else
+  // NOTE:  This code technically allows the queue to grow without bound, 
but in
+  //        practice, the qsize reaches some semi-stable length as texture
+  //        generation requests are produced/consumed by the threads
+  ++nheap;
+  if (nheap>=max_size) {
+    // Save old dataspace, allocate new dataspace
+    char* oldspace=dataspace;
+    dataspace=new char[2*max_size*sizeof(DynPLTMessage)];
+
+    // Copy current elements
+    memcpy(reinterpret_cast<void*>(dataspace),
+           reinterpret_cast<void*>(oldspace),
+           (nheap - 1)*sizeof(DynPLTMessage));
+
+    // Release old dataspace
+    delete [] oldspace;
+
+    // Update heap pointer and max_size
+    heap=reinterpret_cast<DynPLTMessage*>(dataspace);
+    max_size *= 2;
+  }
+
+  // Walk node up the heap until its priority is less than its parent's
+  int i=nheap - 1;
+  int parent=(i + 1)/2 - 1;
+  while (i && heap[parent].priority < msg.priority) {
+    heap[i]=heap[parent];
+    i=parent;
+    parent=(i + 1)/2 - 1;
+  }
+
+  // Insert message
+  heap[i]=msg;
+#endif
+}
+
+DynPLTMessage DynPLTPriorityQ::pop(void)
+{
+  // Grab first message
+  DynPLTMessage msg=heap[0];
+
+  // Rebuild the heap
+  --nheap;
+  heap[0]=heap[nheap];
+  heapify(0, nheap);
+
+  return msg;
+}
+
+void DynPLTPriorityQ::heapify(int i, int nnodes)
+{
+  // Initialize indices of left/right children
+  int highest=i;
+  int l=2*i + 1;
+  int r=l + 1;
+
+  // Find index of node with highest priority
+  if (l<nnodes && heap[l].priority > heap[highest].priority)
+    highest=l;
+
+  if (r<nnodes && heap[r].priority > heap[highest].priority)
+    highest=r;
+
+  // Swap heap[i] and heap[highest]
+  if (highest != i) {
+    DynPLTMessage tmp=heap[i];
+    heap[i]=heap[highest];
+    heap[highest]=tmp;
+    
+    // Recursively build the heap
+    heapify(highest, nnodes);
+  }
+}

Modified: trunk/Engine/Control/DynPLTQueue.h
==============================================================================
--- trunk/Engine/Control/DynPLTQueue.h  (original)
+++ trunk/Engine/Control/DynPLTQueue.h  Wed Jul 19 17:39:48 2006
@@ -4,26 +4,40 @@
 
 #include <MantaTypes.h>
 #include <SCIRun/Core/Thread/Mailbox.h>
+#include <SCIRun/Core/Thread/ConditionVariable.h>
+#include <SCIRun/Core/Thread/Mutex.h>
+#include <SCIRun/Core/Thread/Time.h>
 
 #include <float.h>
 
+using namespace SCIRun;
+
 namespace Manta
 {
   class DynPLTGridSpheres;
 
   struct DynPLTMessage {
-    DynPLTMessage(int particle, const DynPLTGridSpheres* grid) :
+    DynPLTMessage(int particle, Real t, const DynPLTGridSpheres* grid) :
       particle(particle), grid(grid)
     {
-      // Do nothing
+      // Time-stamp only
+      priority=Time::currentSeconds();
+
+      // Time-stamp and distance
+      // priority=Time::currentSeconds() - t;
+
+      // Distance only
+      // priority=DBL_MAX - t;
     }
+
     DynPLTMessage(void) :
-      particle(-1), grid(0)
+      particle(-1), priority(0), grid(0)
     {
       // Do nothing
     }
 
     int particle;
+    double priority;
     const DynPLTGridSpheres* grid;
   };
 
@@ -38,6 +52,8 @@
 
     virtual bool trySend(const DynPLTMessage& msg) = 0;
     virtual void send(const DynPLTMessage& msg) = 0;
+
+    virtual void updatePriority(int particle, Real t) = 0;
   };
 
   class DynPLTFifoQ : public DynPLTQueue
@@ -73,8 +89,42 @@
       mailbox->send(msg);
     }
 
+    void updatePriority(int particle, Real t)
+    {
+      // Do nothing
+    }
+
   private:
     SCIRun::Mailbox<DynPLTMessage>* mailbox;
+  };
+
+  class DynPLTPriorityQ : public DynPLTQueue
+  {
+  public:
+    DynPLTPriorityQ(int size);
+    ~DynPLTPriorityQ(void);
+
+    bool tryReceive(DynPLTMessage& msg);
+    DynPLTMessage receive(void);
+    bool trySend(const DynPLTMessage& msg);
+    void send(const DynPLTMessage& msg);
+    void updatePriority(int particle, Real t);
+
+  private:
+    void push(DynPLTMessage const& msg);
+    DynPLTMessage pop(void);
+    void heapify(int i, int nnodes);
+
+    // Thread control
+    Mutex mutex;
+    ConditionVariable empty;
+    ConditionVariable full;
+
+    // Data variables
+    DynPLTMessage* heap;
+    char* dataspace;
+    unsigned int max_size;
+    unsigned int nheap;
   };
 }
 

Modified: trunk/Engine/Control/DynPLTWorker.cc
==============================================================================
--- trunk/Engine/Control/DynPLTWorker.cc        (original)
+++ trunk/Engine/Control/DynPLTWorker.cc        Wed Jul 19 17:39:48 2006
@@ -6,7 +6,6 @@
 #include <Engine/Control/DynPLTWorker.h>
 #include <Engine/Shadows/HardShadows.h>
 #include <Model/Primitives/DynPLTGridSpheres.h>
-#include <Model/Materials/DynPLTMaterial.h>
 #include <Model/Primitives/Sphere.h>
 #include <SCIRun/Core/Math/MiscMath.h>
 #include <SCIRun/Core/Thread/Semaphore.h>
@@ -588,7 +587,7 @@
 
   // Notify worker to exit
   exitSem=&semaphore;
-  DynPLTMessage fake(-1, 0);
+  DynPLTMessage fake(-1, 0., 0);
   context->queue->send(fake);
 
   // Block the calling thread until the worker's done

Modified: trunk/Model/Primitives/DynPLTGridSpheres.cc
==============================================================================
--- trunk/Model/Primitives/DynPLTGridSpheres.cc (original)
+++ trunk/Model/Primitives/DynPLTGridSpheres.cc Wed Jul 19 17:39:48 2006
@@ -89,10 +89,11 @@
       // Request texture generation, if necessary
       if (!requested[particle]) {
         // Create and post message
-        DynPLTMessage msg(particle, this);
+        DynPLTMessage msg(particle, rays.getMinT(i), this);
         if (queue->trySend(msg))
           requested[particle]=true;
-      }
+      } else
+        queue->updatePriority(particle, rays.getMinT(i));
 
       // Use default ambient light while texture is invalid
       activeLights->getAmbientLight()->computeAmbient(context, sub, ambient);
@@ -135,10 +136,11 @@
       // Request texture generation, if necessary
       if (!requested[particle]) {
         // Create and post message
-        DynPLTMessage msg(particle, this);
+        DynPLTMessage msg(particle, rays.getMinT(i), this);
         if (queue->trySend(msg))
           requested[particle]=true;
-      }
+      } else
+        queue->updatePriority(particle, rays.getMinT(i));
 
       // Use Lambertian shading while texture is invalid
       GridSpheres::shade(context, sub);

Modified: trunk/Model/Primitives/DynPLTGridSpheres.h
==============================================================================
--- trunk/Model/Primitives/DynPLTGridSpheres.h  (original)
+++ trunk/Model/Primitives/DynPLTGridSpheres.h  Wed Jul 19 17:39:48 2006
@@ -102,6 +102,10 @@
       return plts[idx];
     }
 
+    void resetRequested(int idx) {
+      requested[idx]=false;
+    }
+
   private:
     void shadeAmbient(const RenderContext& context, RayPacket& rays) const;
     void shadeGlobal(const RenderContext& context, RayPacket& rays) const;

Modified: trunk/scenes/dynplt.cc
==============================================================================
--- trunk/scenes/dynplt.cc      (original)
+++ trunk/scenes/dynplt.cc      Wed Jul 19 17:39:48 2006
@@ -41,6 +41,7 @@
   string fname="";
   int depth=1;
   bool dilate=false;
+  bool fifo=false;
   int max_depth=3;
   int ncells=2;
   int ngroups=100;
@@ -72,6 +73,8 @@
         throw IllegalArgument("scene dynplt -depth", i, args);
     } else if (arg=="-dilate") {
       dilate=true;
+    } else if (arg=="-fifo") {
+      fifo=true;
     } else if (arg=="-envmap") {
       string s;
       if (!getStringArg(i, args, s))
@@ -135,6 +138,7 @@
       cerr<<"  -cidx <int>                       data value index for color 
mapping\n";
       cerr<<"  -depth <int>                      grid depth\n";
       cerr<<"  -dilate                           dilate textures during 
generation\n";
+      cerr<<"  -fifo                             use fifo queue for texture 
requests\n";
       cerr<<"  -envmap [bg] <string>             environment map filename\n";
       cerr<<"  -i <string>                       particle data filename\n";
       cerr<<"  -nbounces <int>                   number of indirect 
nbounces\n";
@@ -158,9 +162,14 @@
 
   // Create DynPLT work queue
   DynPLTQueue* queue;
-  // XXX:  temporary (should switch on queue type)
-  queue=new DynPLTFifoQ(nthreads*qsize);
-  
+  if (fifo) {
+    queue=new DynPLTFifoQ(nthreads*qsize);
+    cerr<<"Using FIFO Queue\n";
+  } else {
+    queue=new DynPLTPriorityQ(nthreads*qsize);
+    cerr<<"Using Priority Queue\n";
+  }
+
   Background* bg=0;
   if (env_fname != "")
     bg=new EnvMapBackground(env_fname);

---

• [MANTA] r1148 - in trunk: Engine/Control Model/Primitives scenes, cgribble, 07/19/2006

---

Archive powered by MHonArc 2.6.16.