[cadynce] How Many Configurations Is Enough?

[Raj Rajkumar]

Joe and Gautam:

Based on little more than hearsay, I suspect that the word 'dimension' 
may be overloaded in PoR discussions.  In multi-dimensional 
bin-packing,  an object to be packed has a size attribute in k 
orthogonal dimensions, and bins have a unit size in each of these 
dimensions.    In PoR, attributes like security class, OS used, etc. may 
have been discussed as dimensions but are probably just classifiers 
which simplify the bin-packing problem.  As an example, if a software 
module can run only on Windows and another module runs only on (say) 
Linux, it would follow that there are Windows and (say) Linux bins.   
Windows modules can only be allocated to Windows machines, etc.   This 
in turn would segment the larger bin-packing problem into two smaller 
but distinct problems.  

I agree that a longer discussion must be had.

---
Raj

Gautam Thaker wrote:
> Raj Rajkumar wrote:
>> Dear Joe, Gautam and Patrick:
>>
>> On a somewhat different note, the current configuration generator 
>> uses single-dimensional bin-packing.   ARMS-2 results indicated that 
>> relatively simple multi-dimensional variants of classical heuristics 
>> tend to work pretty well.   At CMU, a small group of us (including a 
>> former PhD student of mine named Dr. Dio DeNiz who is now at the SEI) 
>> has been spending some time reading and studying the worst-case 
>> behaviors of multi-dimensional bin-packing. There are some surprising 
>> (i.e. negative) performance bounds out there on multi-dimensional 
>> bin-packing.   Briefly, if we have k dimensions, a polynomial-time 
>> heuristic may require as many (k+1) times as many processors as 
>> required by the optimal packing.   The lower bound is 150% (i.e. 50% 
>> more processors than the optimal).    Initially, we thought that the 
>> upper bound was perhaps pessimistic, but after playing around with 
>> some numbers, we found one case with k=3 dimensions, the optimal 
>> requires two bins while a fairly smart heuristic (the one that Gaurav 
>> used in ARMS-2) required 4 processors.  In other words, we required 
>> (k-1) times more processors than the optimal.   Please note that 
>> these are worst-case (pathological) scenarios.   We continue to 
>> believe that in practice, multi-dimensional packing heuristics will 
>> do well in general and an ensemble will do incredibly better.  For 
>> example, for the above case, WFD solved it quickly to get the 
>> optimal! It may stumble on other cases however - encouraging the use 
>> of ensembles.
>>
>> Two takeaways:
>>
>> 1. With multi-dimensional bin-packing, there may be scenarios where 
>> the number of processors required can be significantly higher than 
>> what one might have come to expect.
>> 2. An ensemble of multi-dimensional bin-packing heuristics will do well.
>
> Hi Raj:
>
> When I met with Carol Galloway and others at NSWC Dahlgren on May 2nd 
> one of the points Paul Werme asked me about was this exact issues. He 
> worried that PoR may have as many as 10 dimensions to pack and he 
> worried if that presented problems to allocators. I had replied that 
> more the dimensions more difficult things will be but that I will 
> discuss this point within the cadynce community. Glad this has come 
> up. I had also said that this being "Box 2", meaning off line 
> analysis, we did not mind spending lots of CPU time to generate 
> candidate allocations.
>
> I think we can address this point in coming weeks but nothing much can 
> be done this week. Perhaps we can talk about this in depth if and when 
> we convene the cadynce team for the next face to face meeting. I 
> remain of hope that for most practical cases we can find solutions 
> given that this is offline (box 2).
>
> Gautam
>
>>
>> ---
>> Raj
>>
>> _______________________________________________
>> Cadynce mailing list
>> Cadynce at list.isis.vanderbilt.edu
>> http://list.isis.vanderbilt.edu/mailman/listinfo/cadynce
>