[cadynce] How Many Configurations Is Enough?

[Raj Rajkumar]

I hasten to add that some dimensions (like CPU cycles and memory 
requirements, perhaps FLASH and DRAM needs)  in the PoR discussions will 
certainly be dimensions in the mathematical bin-packing sense.

---
Raj

Raj Rajkumar wrote:
> 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
>>
>
> _______________________________________________
> Cadynce mailing list
> Cadynce at list.isis.vanderbilt.edu
> http://list.isis.vanderbilt.edu/mailman/listinfo/cadynce