Text archives Help

---

Author: cgribble
Date: Thu Jul 20 12:00:06 2006
New Revision: 1150

Modified:
   trunk/Engine/Control/DynPLTQueue.cc
   trunk/Engine/Control/DynPLTQueue.h
   trunk/Model/Groups/TimeSteppedParticles.cc
   trunk/Model/Primitives/DynPLTGridSpheres.cc
   trunk/Model/Primitives/DynPLTGridSpheres.h
   trunk/scenes/dynplt.cc
Log:
scenes/dynplt.cc
  Added "-lifo" to cmdln option help menu print-out thingy...
  Corrected queue type message for LIFO queue

Model/Groups/TimeSteppedParticles.cc
  Added call to DynPLTQueue::resizeHeapIdx (only does something interesting 
for
    PriorityQ; others are no-ops)

Model/Primitives/DynPLTGridSpheres.cc
Model/Primitives/DynPLTGridSpheres.h
  Made priority computation a new member function
  Changed requested from vector<bool> to vector<double>; now stores priorities
    (non-zero entry implies that the particle's texture has been requested)
  Toyed around with many different schemes for updating priorities, etc. and
    settled on the following:  priorities for previously requested but still
    invalid textures are not updated before some predetermined period of time
    (currently 5 seconds); even with constant time updates (see below), 
updating
    the priorities every frame is too costly; 5 seconds is reasonably 
responsive
    to user interactions, but +/- some delta might be fine, too

Engine/Control/DynPLTQueue.cc
Engine/Control/DynPLTQueue.h
  Moved priority computation from DynPLTMessage constructor to 
DynPLTGridSpheres
    member function (see above)
  Calls to updatePriority(...) were, in fact, responsible for the slow downs 
in
    the "grow-without-bound" case (linear search through heap was causing
    problems for large datasets); added array to track current heap index for
    each particle to allow constant time updates
  Made updatePriority(...) and resizeHeapIdx(...) no-ops in DynPLTQueue base
   class to prevent uniterested classes from having to implement their own 
no-op
   versions
  Added heap_idx array to PriorityQ:  stores current index into heap of each
    particle (-1 if not in heap); enables constant time priority updates at 
the
    cost of additional memory (4 bytes/particle)
  Added resizeHeapIdx(...) implementation to PriorityQ:  resizes heap_idx 
array
    to number of particles and initializes entries to -1


Modified: trunk/Engine/Control/DynPLTQueue.cc
==============================================================================
--- trunk/Engine/Control/DynPLTQueue.cc (original)
+++ trunk/Engine/Control/DynPLTQueue.cc Thu Jul 20 12:00:06 2006
@@ -11,8 +11,6 @@
   mutex("LifoQ lock"), empty("LifoQ empty condition"),
   full("LifoQ full condition"), top(-1), max_size(size)
 {
-  cerr<<"max_size = "<<max_size<<'\n';
-
   // Allocate dataspace
   dataspace=new char[max_size*sizeof(DynPLTMessage)];
   queue=reinterpret_cast<DynPLTMessage*>(dataspace);
@@ -107,6 +105,10 @@
 
   // Free dataspace
   delete [] dataspace;
+
+#ifndef FIXED_SIZE_QUEUE
+  delete [] heap_idx;
+#endif
 }
 
 bool DynPLTPriorityQ::tryReceive(DynPLTMessage& msg)
@@ -171,22 +173,20 @@
   mutex.unlock();
 }
 
-void DynPLTPriorityQ::updatePriority(int particle, Real t)
+void DynPLTPriorityQ::updatePriority(int particle, double priority)
 {
-  // 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?
+#ifdef FIXED_SIZE_QUEUE
   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);
+      DynPLTMessage msg(particle, priority, 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) {
+      while (i && heap[parent].priority < priority) {
         heap[i]=heap[parent];
         i=parent;
         parent=(i + 1)/2 - 1;
@@ -200,11 +200,38 @@
   }
 
   mutex.unlock();
+#else
+  mutex.lock();
+
+  int idx=heap_idx[particle];
+  if (idx>-1) {
+    // Found particle, create new message with updated priority
+    DynPLTMessage msg(particle, priority, heap[idx].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=(idx + 1)/2 - 1;
+    while (idx && heap[parent].priority < priority) {
+      // Swap parent
+      heap[idx]=heap[parent];
+      heap_idx[heap[idx].particle]=idx;
+
+      idx=parent;
+      parent=(idx + 1)/2 - 1;
+    }
+
+    // Insert message and update heap_idx
+    heap[idx]=msg;
+    heap_idx[particle]=idx;
+  }
+
+  mutex.unlock();
+#endif
 }
 
 void DynPLTPriorityQ::push(DynPLTMessage const& msg)
 {
-#if 0
+#ifdef FIXED_SIZE_QUEUE
   // 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...
@@ -221,7 +248,7 @@
       parent=(i + 1)/2 - 1;
     }
 
-    // Insert message
+    // Insert message and update heap_idx
     heap[i]=msg;
   } else {
     // Drop last node
@@ -235,9 +262,9 @@
     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
+  // NOTE:  In theory, the following code allows the queue to grow without 
bound.
+  //        However, in practice, the heap reaches some semi-stable size as
+  //        texture generation requests are produced/consumed by the threads
   ++nheap;
   if (nheap>=max_size) {
     // Save old dataspace, allocate new dataspace
@@ -255,6 +282,11 @@
     // Update heap pointer and max_size
     heap=reinterpret_cast<DynPLTMessage*>(dataspace);
     max_size *= 2;
+
+    /*
+    cerr<<"Heap is now "<<max_size*sizeof(DynPLTMessage)<<" bytes 
("<<max_size
+        <<" messages)\n";
+    */
   }
 
   // Walk node up the heap until its priority is less than its parent's
@@ -262,12 +294,15 @@
   int parent=(i + 1)/2 - 1;
   while (i && heap[parent].priority < msg.priority) {
     heap[i]=heap[parent];
+    heap_idx[heap[i].particle]=i;
+
     i=parent;
     parent=(i + 1)/2 - 1;
   }
 
-  // Insert message
+  // Insert message and update heap_idx
   heap[i]=msg;
+  heap_idx[msg.particle]=i;
 #endif
 }
 
@@ -275,10 +310,16 @@
 {
   // Grab first message
   DynPLTMessage msg=heap[0];
+#ifndef FIXED_SIZE_QUEUE
+  heap_idx[msg.particle]=-1;
+#endif
 
   // Rebuild the heap
   --nheap;
   heap[0]=heap[nheap];
+#ifndef FIXED_SIZE_QUEUE
+  heap_idx[heap[0].particle]=0;
+#endif
   heapify(0, nheap);
 
   return msg;
@@ -303,6 +344,10 @@
     DynPLTMessage tmp=heap[i];
     heap[i]=heap[highest];
     heap[highest]=tmp;
+#ifndef FIXED_SIZE_QUEUE
+    heap_idx[heap[i].particle]=i;
+    heap_idx[heap[highest].particle]=highest;
+#endif
     
     // Recursively build the heap
     heapify(highest, nnodes);

Modified: trunk/Engine/Control/DynPLTQueue.h
==============================================================================
--- trunk/Engine/Control/DynPLTQueue.h  (original)
+++ trunk/Engine/Control/DynPLTQueue.h  Thu Jul 20 12:00:06 2006
@@ -6,32 +6,20 @@
 #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>
-
-// XXX:  temporary
-#include <iostream>
-using std::cerr;
 
 using namespace SCIRun;
 
+// #define FIXED_SIZE_QUEUE
+
 namespace Manta
 {
   class DynPLTGridSpheres;
 
   struct DynPLTMessage {
-    DynPLTMessage(int particle, Real t, const DynPLTGridSpheres* grid) :
-      particle(particle), grid(grid)
+    DynPLTMessage(int particle, double priority, const DynPLTGridSpheres* 
grid) :
+      particle(particle), priority(priority), grid(grid)
     {
-      // Time-stamp only
-      priority=Time::currentSeconds();
-
-      // Time-stamp and distance
-      // priority=Time::currentSeconds() - t;
-
-      // Distance only
-      // priority=DBL_MAX - t;
+      // Do nothing
     }
 
     DynPLTMessage(void) :
@@ -57,7 +45,8 @@
     virtual bool trySend(const DynPLTMessage& msg) = 0;
     virtual void send(const DynPLTMessage& msg) = 0;
 
-    virtual void updatePriority(int particle, Real t) = 0;
+    virtual void updatePriority(int particle, double priority) { /* no-op */ 
}
+    virtual void resizeHeapIdx(unsigned int nparticles_) { /* no-op */ }
   };
 
   class DynPLTFifoQ : public DynPLTQueue
@@ -93,8 +82,6 @@
       mailbox->send(msg);
     }
 
-    void updatePriority(int particle, Real t) { /* no-op */ }
-
   private:
     SCIRun::Mailbox<DynPLTMessage>* mailbox;
   };
@@ -110,8 +97,6 @@
     bool trySend(const DynPLTMessage& msg);
     void send(const DynPLTMessage& msg);
 
-    void updatePriority(int particle, Real t) { /* no-op */ }
-
   private:
     void push(DynPLTMessage const& msg) { queue[++top]=msg; }
     DynPLTMessage pop(void) { return queue[top--]; }
@@ -138,7 +123,17 @@
     DynPLTMessage receive(void);
     bool trySend(const DynPLTMessage& msg);
     void send(const DynPLTMessage& msg);
-    void updatePriority(int particle, Real t);
+
+    void updatePriority(int particle, double priority);
+#ifndef FIXED_SIZE_QUEUE
+    void resizeHeapIdx(unsigned int nparticles_)
+    {
+      nparticles=nparticles_;
+      heap_idx=new int[nparticles];
+      for (unsigned int i=0; i<nparticles; ++i)
+        heap_idx[i]=-1;
+    }
+#endif
 
   private:
     void push(DynPLTMessage const& msg);
@@ -155,6 +150,10 @@
     char* dataspace;
     int max_size;
     int nheap;
+#ifndef FIXED_SIZE_QUEUE
+    int* heap_idx;
+    unsigned int nparticles;
+#endif
   };
 }
 

Modified: trunk/Model/Groups/TimeSteppedParticles.cc
==============================================================================
--- trunk/Model/Groups/TimeSteppedParticles.cc  (original)
+++ trunk/Model/Groups/TimeSteppedParticles.cc  Thu Jul 20 12:00:06 2006
@@ -1,6 +1,7 @@
 
 #include <Core/Exceptions/InputError.h>
 #include <Core/Exceptions/OutputError.h>
+#include <Engine/Control/DynPLTQueue.h>
 #include <Model/Groups/TimeSteppedParticles.h>
 #include <Model/Primitives/GridSpheres.h>
 #include <Model/Readers/ParticleNRRD.h>
@@ -25,6 +26,7 @@
   if (pos != string::npos) {
     ParticleNRRD pnrrd(filename);
     if (queue) {
+      queue->resizeHeapIdx(pnrrd.getNParticles());
       add(new DynPLTGridSpheres(queue, pnrrd.getParticleData(),
                                 pnrrd.getNParticles(), pnrrd.getNVars(), 
ncells,
                                 depth, radius, ridx, cmap, cidx));

Modified: trunk/Model/Primitives/DynPLTGridSpheres.cc
==============================================================================
--- trunk/Model/Primitives/DynPLTGridSpheres.cc (original)
+++ trunk/Model/Primitives/DynPLTGridSpheres.cc Thu Jul 20 12:00:06 2006
@@ -13,6 +13,8 @@
 using namespace Manta;
 using namespace SCIRun;
 
+#define UPDATE_TIME 5.
+
 DynPLTGridSpheres::DynPLTGridSpheres(DynPLTQueue* queue,
                                      float* spheres, int nspheres, int nvars,
                                      int ncells, int depth, Real radius,
@@ -27,7 +29,7 @@
   requested.resize(nspheres);
   for (unsigned int i=0; i<nspheres; ++i) {
     plts[i]=0;
-    requested[i]=false;
+    requested[i]=0.;
     allocated[i]=false;
     valid[i]=false;
   }
@@ -87,13 +89,24 @@
       }
     } else {
       // Request texture generation, if necessary
-      if (!requested[particle]) {
+      if (requested[particle]==0.) {
         // Create and post message
-        DynPLTMessage msg(particle, rays.getMinT(i), this);
+        double priority=computePriority(rays.getMinT(i));
+        DynPLTMessage msg(particle, priority, this);
         if (queue->trySend(msg))
-          requested[particle]=true;
-      } else
-        queue->updatePriority(particle, rays.getMinT(i));
+          requested[particle]=priority;
+      } else {
+#if 1
+        // Update priority only after UPDATE_TIME seconds
+        if (Time::currentSeconds() - requested[particle] > UPDATE_TIME) {
+          requested[particle]=computePriority(rays.getMinT(i));
+          queue->updatePriority(particle, requested[particle]);
+        }
+#else
+        requested[particle]=computePriority(rays.getMinT(i));
+        queue->updatePriority(particle, requested[particle]);
+#endif
+      }
 
       // Use default ambient light while texture is invalid
       activeLights->getAmbientLight()->computeAmbient(context, sub, ambient);
@@ -134,13 +147,24 @@
       }
     } else {
       // Request texture generation, if necessary
-      if (!requested[particle]) {
+      if (requested[particle]==0.) {
         // Create and post message
-        DynPLTMessage msg(particle, rays.getMinT(i), this);
+        double priority=computePriority(rays.getMinT(i));
+        DynPLTMessage msg(particle, priority, this);
         if (queue->trySend(msg))
-          requested[particle]=true;
-      } else
-        queue->updatePriority(particle, rays.getMinT(i));
+          requested[particle]=priority;
+      } else {
+#if 1
+        // Update priority only after UPDATE_TIME seconds
+        if (Time::currentSeconds() - requested[particle] > UPDATE_TIME) {
+          requested[particle]=computePriority(rays.getMinT(i));
+          queue->updatePriority(particle, requested[particle]);
+        }
+#else
+        requested[particle]=computePriority(rays.getMinT(i));
+        queue->updatePriority(particle, requested[particle]);
+#endif
+      }
 
       // 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  Thu Jul 20 12:00:06 2006
@@ -4,10 +4,13 @@
 
 #include <Model/Primitives/GridSpheres.h>
 #include <SCIRun/Core/Thread/Mailbox.h>
+#include <SCIRun/Core/Thread/Time.h>
 
 #include <vector>
 using std::vector;
 
+#include <float.h>
+
 #define XRES 16
 #define YRES 16
 
@@ -101,9 +104,20 @@
     DynPLT* getTexture(int idx) {
       return plts[idx];
     }
+    
+    double computePriority(Real t) const {
+      // Time-stamp only
+      return SCIRun::Time::currentSeconds();
+
+      // Distance only (closest first)
+      // return DBL_MAX - t;
+
+      // Time-stamp and distance
+      // return SCIRun::Time::currentSeconds() - t;
+    }
 
     void resetRequested(int idx) {
-      requested[idx]=false;
+      requested[idx]=0.;
     }
 
   private:
@@ -121,7 +135,7 @@
     }
 
     DynPLTQueue* queue;
-    mutable vector<bool> requested;
+    mutable vector<double> requested;
     vector<bool> allocated;
     vector<bool> valid;
     vector<DynPLT*> plts;

Modified: trunk/scenes/dynplt.cc
==============================================================================
--- trunk/scenes/dynplt.cc      (original)
+++ trunk/scenes/dynplt.cc      Thu Jul 20 12:00:06 2006
@@ -146,6 +146,7 @@
       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<<"  -lifo                             use lifo queue for texture 
requests\n";
       cerr<<"  -nbounces <int>                   number of indirect 
nbounces\n";
       cerr<<"  -ncells <int>                     grid resolution\n";
       cerr<<"  -ngroups <int>                    number of sample groups\n";
@@ -172,7 +173,7 @@
     cerr<<"Using FIFO Queue\n";
   } else if (lifo) {
     queue=new DynPLTLifoQ(nthreads*qsize);
-    cerr<<"Using FIFO Queue\n";
+    cerr<<"Using LIFO Queue\n";
   } else {
     queue=new DynPLTPriorityQ(nthreads*qsize);
     cerr<<"Using Priority Queue\n";

---

• [MANTA] r1150 - in trunk: Engine/Control Model/Groups Model/Primitives scenes, cgribble, 07/20/2006

---

Archive powered by MHonArc 2.6.16.