Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[eerr]

after reading a few documents about multithreading.
it seems that multithreading isn't as difficult as i previously though, and maybe not as difficult as toady thought.

in the following examples(referring to something i did not write myself, and which is in fact one of the few examples i understand!)

the major problems are from order of execution. part of a thread runs in the middle of another thread(literally running between the lines of another part of the program)

in the example they wrote-
there is one instance variable with a default value of 0, and 20 created threads sharing it.
the following threads 0-19  loop around, adding 10, then subtracting  10 a thousand times.

within a single block of code

simultaneously, or rather, between the  functional lines of the other programs, the threads write the value of the instance variable.

the program printed these results:

booThread0 sees the number: 0
booThread1 sees the number: 0
booThread2 sees the number: 0
booThread3 sees the number: 0
booThread4 sees the number: 10
booThread6 sees the number: 10
booThread7 sees the number: 10
booThread8 sees the number: 10
booThread9 sees the number: 10
booThread10 sees the number: 0
booThread11 sees the number: 0
booThread12 sees the number: 0
booThread13 sees the number: 0
booThread5 sees the number: 0
booThread14 sees the number: 0
booThread15 sees the number: 0
booThread16 sees the number: 0
booThread17 sees the number: 0
booThread18 sees the number: 0
booThread19 sees the number: 0
booThread0 sees the number: 0
booThread1 sees the number: 0
booThread3 sees the number: 0
booThread4 sees the number: 0
booThread6 sees the number: 0
booThread8 sees the number: 0
booThread9 sees the number: 0
booThread2 sees the number: 0
booThread7 sees the number: 0
booThread10 sees the number: 10
booThread11 sees the number: 0
booThread12 sees the number: -10
booThread13 sees the number: -10
booThread5 sees the number: -10
booThread14 sees the number: -10
booThread16 sees the number: -10
booThread17 sees the number: -10
booThread18 sees the number: -10
booThread19 sees the number: -10



of course, this is in java, and multithreading in C or C++ is probably more difficult.>

also
just to keep it straight, i don't know multithreading, this example just spoke to me very logically, from the site http://docs.rinet.ru/JWP/ch16.htm


----

new entry:
since we don't know toady's formula, we can only make vague passes as to how it works
there is one problem that i cannot beat easily in the following example:
when dwarves collide.
yet.

dwarf fortress one tile tall and wide: most everything but pathfinding breaks!

assume a single array, containing the passable/impassable value for all tiles

for a dwarf to determine if he can get from point a to point b, he must check all tiles inbetween.

for two dwarves to determine  if they can get from point a to point b, they must both check all tiles inbetween, which may overlap.

what happens if two threads of a multiprocessor try to access the same data at the same time?
does it even happen??

jeeze i think i'll need to come back to this when i know C.

check back this weekend as i ponder and do research


also, bear in mind that my theories are only for me to learn, not that i think toady should really implement multithreading...

[SolarShado]

in my (limited) experience, EVERYthing's harder in C than Java.

and multithreading's been talked to death before. i've not read the reasons it won't work, but apparently, many smart people have decided that it's currently too much trouble.

[Steely Glint]

Also, a program with multiple threads about twice as hard to debug as one with a single thread.

[David Holmes]

It's not that the concept of creating multiple threads and running them is hard, or even that the basic concepts of synchronization are hard in isolated anecdotes.

The problems are that 1) some algorithms are intrinsically hard or impossible to parallelize simply due to their nature, and 2) designing a program with complex synchronization is vastly more work than designing a single-threaded program.  There are a whole host of problems that come up in multi-threaded programs which aren't a  concern in single-threaded program.

You can create multiple threads, but so long as those threads access the same resources, the interactions have to be carefully thought out and synchronized.  In general one thread manipulating a data structure requires that data structure to be consistent for a duration of time, meaning any other threads accessing it have to wait.  In the simplest cases, this negates all benefits of multithreading because in practice, only one thread is running at a time for the computationally hard parts of the program.  Designing a program so that they can all _really_ work at once can be an order of magnitude more work.

That said, I do think that parallelization is probably possible and could probably improve the performance of DF dramatically as number of CPU cores increases, and probably could in some simple ways even now.  But it's not a trivial amount of work.

[sproingie]

C++ multithreading can be about as simple as it is in Java, because there's numerous ports of Java's thread API to C++.  In fact, Java's thread API really isn't much more than raw pthreads.

That's the good news.  The bad news is that multithreading isn't all that trivial.  Multiple pathfinding tasks could probably be moved to threads pretty easily though.  The main thread would still have to block on all of them completing, but they'd at least execute in parallel.  The GUI would be nice on a separate thread, but it's actually really tricky to synchronize in a game.  Besides, I doubt it takes all that much CPU.

[The-Moon]

You need to make mutithreading when you first start working on a game. You cant just decide half way through that your going to add in mutithreading. That could end up becomming a whole rewrite of the whole game.

[woose1]

That could end up becomming a whole rewrite of the whole game.

Hey, didn't we do that with 23a? 

Not a total re-write, but most of the engine was scrapped.

[Sowelu]

I'd say "twice as hard to debug" is very, very generous.  I normally put the number at about ten times.

However I do think it's possible to implement without a total rewrite.

It's often hard to even isolate "what parts of the game are possible to multithread".  Things like temperature could probably have been written multithreaded with a LOT of foresight and planning and an ultimately slightly more limited system, but it's surely out of reach for the moment.  Pathfinding on the other hand, should only be 'hard' and not 'mind-numbingly difficult'.

[Draco18s]

AGAIN?

Don't you people use the search feature of the forums?

[profit]

AGAIN?

Don't you people use the search feature of the forums?

Just shows its a glaring and annoying problem.  Same with the mine cart threads showing hauling is broke.

[eerr]

AGAIN?

Don't you people use the search feature of the forums?

if my post was actually fruitfull, it would quickly loose peoples interest to dig through so many other posts.

I also am too lazy to use it, just as other people would have to be over 10X less lazy than me to reread 100 posts to find mine.

[Ampersand]

Multithreading probably won't happen at this stage of development. That isn't to say that Toady might at some future point decide to implement it as resources become more widely available, and the programming tasks involved become more readily implementable, but for the moment, it does not make sense to dedicate the necessary amount of work required to do this while things are still being added to the game with every release.

When it comes to path finding, though, a small degree of multithreading might happen sooner rather than later in sort of the style the new graphics acceleration came about, just because the current path finding model as it stands is terribly inefficient. However, all of this may become more or less moot in due time as processing speed increases. Moore's law has plenty of opportunity to meet the original standard of doubling processing speed every year in the next few years due to a variety of innovations.

Probabilistic chips, for example are a recent innovation, which surpass Moore's law. If you were to take current processor, and do nothing to it except some how change it to the new probabilistic model, keeping the same number of transistors and clock speed, it's performance in terms of floating points per second would septuple. Seven times faster. This is a technology that is available now, and should be on the market relatively soon

There is a trade off, though, in that they are not as precise. What this means isn't obvious to people who aren't computer scientists, but what it means is this. Suppose you're running a program in which it's doing a lot of calculations that present fractional products, such as drawing a circle. The pixels that define the edges of the circle will have definite integer positions on the canvas grid, but the processor does not know this. It calculates the edge points of the circle exactly as it would be if it were on paper, most points fractional. These must be rounded out in the program in order to get the integer positions. The probabilistic computer, however, will only go through so many significant figures before it moves on.

For example, on a grid moving a pixel 3.2446453332159 pixels to the right is meaningless. That amount of precision is unnecessary, as pixels are indivisible, but an ordinary processor would still produce that as an answer in it's calculations anyway, eating up precious CPU time. The new probabilistic model throws out that high degree of precision and thus still returns the "correct" answer (in that it would be the same as the original after the necessary rounding) in less time.

[Draco18s]

AGAIN?

Don't you people use the search feature of the forums?

if my post was actually fruitfull, it would quickly loose peoples interest to dig through so many other posts.

I also am too lazy to use it, just as other people would have to be over 10X less lazy than me to reread 100 posts to find mine.

That's what a "new" button is for.  It jumps strait to new posts.  Thus a resurrected thread that has been previously read will have people only reading your post.

OTOH I'd have berated you for resurrecting the thread as you clearly didn't read the fact that Toady has no interest, desire, or knowledge of how to multithread an application.

[Tormy]

AGAIN?

Don't you people use the search feature of the forums?

I also am too lazy to use it, just as other people would have to be over 10X less lazy than me to reread 100 posts to find mine.

That's a really bad excuse...

[Granite26]

just insulting and rude, really