[Openmcl-devel] Quick HW question...

[Ron Garret]

http://en.wikipedia.org/wiki/Curse_of_dimensionality

On Nov 17, 2010, at 12:02 PM, Jon Anthony wrote:

> 
> I'm not sure I understand the situation either, but I'll blunder in as
> well.  I've spent quite a bit of time and effort on what might be called
> "multidimensional graphs" - basically a node participates in many
> orthogonal graphs (the dimensions).  The number of graphs (dimensions)
> can be quite high, and the degree for a node in many of them can be
> quite high (100's, 1000's, even 100's of thousands).  By sheer force of
> magnitude, it is difficult to keep all those nodes along all the
> dimensions localized.
> 
> /Jon
> 
> 
> On Wed, 2010-11-17 at 18:09 +0000, Tim Bradshaw wrote:
>> On 17 Nov 2010, at 17:47, Spires, Shannon V wrote:
>> 
>>> You're wrong only because I was too vague in my initial comment: I'm biased toward programs that build large n-dimensional graph data structures and then grovel them, since I find those kind of problems interesting and that's what I'm paid to do. You can write those programs in any language, but I prefer Lisp. The point is that when n (the number of inherent dimensions of your data structure) is greater than 1, it's impossible to compact that data into a one-dimensional memory structure that localizes all the dimensions, no matter how smart your GC is. So for these kinds of programs, you're hosed with conventional architectures where caches are one-dimensional. Whether you're using C, Lisp, Cobol, or anything else.
>> 
>> I'm not sure I understand this really, but I'll blunder in.  If what you're saying is that your programs have inherently random memory behaviour, then I think yes, you're hosed, and further there's nothing (short of changing the laws of physics) which will help you as far as I can see.
>> 
>> If there *is* locality in your code, then I think it's possible to exploit that locality.  I  obviously don't understand your systems, but if you have something which is walking around in some space (of whatever dimension), for which you have some kind of metric (or even some weaker notion of "closeness" than a metric), then if you have a system which can allocate objects which are close in this space close to each other in terms the system understands (on the same cache line, or in memory close to the processor doing the work, or what have you), then you can exploit this metric.
>> 
>> 
> 
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel