performance of hardware dynamic scheduling
|
From: Terje Mathisen on 30 Mar 2008 08:25 Nick Maclaren wrote: > In article <Uu6dneNs3YKI6HLanZ2dnUVZ_oSunZ2d(a)giganews.com>, > Terje Mathisen <terje.mathisen(a)hda.hydro.com> writes: > |> I believe the latest HPC oil codes are moving in this direction. > > I didn't know that, but it doesn't surprise me. Don't quote me, it might be totally bogus, I just read an article which sort of indicated moving in this direction. Terje -- - <Terje.Mathisen(a)hda.hydro.com> "almost all programming can be viewed as an exercise in caching"
From: John Dallman on 30 Mar 2008 10:42 In article <fsnmaa$r3g$1(a)gemini.csx.cam.ac.uk>, nmm1(a)cus.cam.ac.uk (Nick Maclaren) wrote: > In article <1ielzej.18dmntm1moby6hN%nospam(a)ab-katrinedal.dk>, > nospam(a)ab-katrinedal.dk (=?ISO-8859-1?Q?Niels_J=F8rgen_Kruse?=) > writes: > > Smells like the problem is that you modify the datastructures > > that you search, in order to speed up searches? > > > > You could have 2 versions of the search, one that improve the data > > structures and one that don't. Using the former a percentage of > > the time would be enough to evolve the data structures. > > Eh? I understood John Dallman to mean that the data structures are > essentially read-only, but are being accessed in a most cache- > unfriendly way. That is the normal characteristic of such programs > - and they are not rare. You're correct in this. Each element of the data structure is a member of several linked lists, any of which may be the principal search route. They have to be linked lists, because they are broken up into many sub-groups, but the number of elements in a sub-group may be very large, although it is usually quite small. We tried doing it with arrays in the FORTRAN version, 1970-85. We aren't going back to that. > As I have posted before, there are some fairly basic algorithms that > are provably of that form - i.e. mathematically unoptimisable. The > only real hope for a considerable speedup in those cases is to solve > the problem using an entirely different mathematical model - which is > quite often possible, but needs a VERY high calibre of person to do > the transformation! We keep looking for such a way to do it, as people get cross with the current way after a few years of working on it. We've never managed to find one that was practical. There is a brute-force method that looks tenable with memories of something like 10^18 bytes, but not in anything smaller. -- John Dallman, jgd(a)cix.co.uk, HTML mail is treated as probable spam.
From: Nick Maclaren on 30 Mar 2008 14:10 In article <memo.20080330154221.1748A(a)jgd.compulink.co.uk>, jgd(a)cix.co.uk (John Dallman) writes: |> |> You're correct in this. Each element of the data structure is a member |> of several linked lists, any of which may be the principal search route. |> They have to be linked lists, because they are broken up into many |> sub-groups, but the number of elements in a sub-group may be very large, |> although it is usually quite small. We tried doing it with arrays in the |> FORTRAN version, 1970-85. We aren't going back to that. Handling such structures in Fortran 77 was a right pain! Modern Fortran isn't bad. |> We keep looking for such a way to do it, as people get cross with the |> current way after a few years of working on it. We've never managed to |> find one that was practical. There is a brute-force method that looks |> tenable with memories of something like 10^18 bytes, but not in anything |> smaller. That situation is a common characteristic of such algorithms! Regards, Nick Maclaren.
From: Terje Mathisen on 30 Mar 2008 16:21 John Dallman wrote: > In article <fsnmaa$r3g$1(a)gemini.csx.cam.ac.uk>, nmm1(a)cus.cam.ac.uk (Nick > Maclaren) wrote: >> Eh? I understood John Dallman to mean that the data structures are >> essentially read-only, but are being accessed in a most cache- >> unfriendly way. That is the normal characteristic of such programs >> - and they are not rare. > > You're correct in this. Each element of the data structure is a member > of several linked lists, any of which may be the principal search route. > They have to be linked lists, because they are broken up into many > sub-groups, but the number of elements in a sub-group may be very large, > although it is usually quite small. We tried doing it with arrays in the > FORTRAN version, 1970-85. We aren't going back to that. > >> As I have posted before, there are some fairly basic algorithms that >> are provably of that form - i.e. mathematically unoptimisable. The >> only real hope for a considerable speedup in those cases is to solve >> the problem using an entirely different mathematical model - which is >> quite often possible, but needs a VERY high calibre of person to do >> the transformation! > > We keep looking for such a way to do it, as people get cross with the > current way after a few years of working on it. We've never managed to > find one that was practical. There is a brute-force method that looks > tenable with memories of something like 10^18 bytes, but not in anything > smaller. I love looking at this sort of stuff, I'd be quite happy if you could send me a private mail with a problem/algorithm description. I'm warning you though, I doubt that I'll be able to come up with any major & portable speedups. :-( Terje -- - <Terje.Mathisen(a)hda.hydro.com> "almost all programming can be viewed as an exercise in caching"
From: John Dallman on 30 Mar 2008 16:55
In article <gd6dnZ6-4PCta3LanZ2dnUVZ8s3inZ2d(a)giganews.com>, terje.mathisen(a)hda.hydro.com (Terje Mathisen) wrote: > > We keep looking for such a way to do it, as people get cross with > > the current way after a few years of working on it. We've never > > managed to find one that was practical. There is a brute-force > > method that looks tenable with memories of something like 10^18 > > bytes, but not in anything smaller. > > I love looking at this sort of stuff, I'd be quite happy if you could > send me a private mail with a problem/algorithm description. Thanks, but it's not just one or two algorithims. I'll send you mail sometime this week. -- John Dallman, jgd(a)cix.co.uk, HTML mail is treated as probable spam. |