Print

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

[soulsource]

[...]
There is, however another approach, which, from my (albeit limited) research, doesn't typically require a complete redesign.  One offloads computationally intensive tasks to other cores (from my understanding path finding is the big one for DF), and the cores report when they've completed the work.

This idea can be followed even further. Since pathfinding has to be done for many creatures, CPU threads all operate on the same memory (aka: nearly no extra RAM needed), and the pathfinding of one creature does not interfere with the pathfinding of others (as a first, and probably good enough approximation), it does not sound to unreasonable to me, to have several pathfinding-threads running. Nevertheless this probably requires a complete rewrite of the pathfinding code and also the pathfinding threads have to be synchronized, probably every tick. Parallelizing calculations on such a low level might be the most work intensive way of using multi-core CPUs, but it's in my opinion the "proper" way.

With the advent of unified address space, even GPGPU computation might be considered worthwhile for pathfinding or temperature calculations, yet this definitely requires a complete rewrite, and only very recent hardware can profit from it (given that without unified address space the fort layout would have to be copied between CPU and GPU memory regularly...).

[Quietust]

works rather well, (occasional BSOD).

I wouldn't consider an "occasional BSOD" to be working "rather well" - a STOP error is generally caused by a poorly-written driver or faulty hardware and is a sign of a major problem with your computer. Whereas bluescreens were a part of life in Windows 95/98/Me, on Windows NT in general (this includes 2000, XP, Vista, 7, 8, 8.1, and beyond) they shouldn't ever happen.

[wuphonsreach]

works rather well, (occasional BSOD).

I wouldn't consider an "occasional BSOD" to be working "rather well" - a STOP error is generally caused by a poorly-written driver or faulty hardware and is a sign of a major problem with your computer. Whereas bluescreens were a part of life in Windows 95/98/Me, on Windows NT in general (this includes 2000, XP, Vista, 7, 8, 8.1, and beyond) they shouldn't ever happen.

A good test is Prime95 - it has a "torture test" mode which uses a lot of RAM and stresses out the CPU and L1-L3 caches.  It will tell you if you can run without errors at the speeds you have configured. It is better then MemTest/MemTest86+ at finding timing problems.

Run it overnight, if it runs for 8+ hours without issues... you are likely okay.

[Loci]

works rather well, (occasional BSOD).

I wouldn't consider an "occasional BSOD" to be working "rather well" - a STOP error is generally caused by a poorly-written driver or faulty hardware and is a sign of a major problem with your computer. Whereas bluescreens were a part of life in Windows 95/98/Me, on Windows NT in general (this includes 2000, XP, Vista, 7, 8, 8.1, and beyond) they shouldn't ever happen.

Nonsense. Consider NASA: when they wanted an absolutely reliable computer system, they included multiple redundant computers instead of one golden machine. Despite the obvious complexities involved in redundancy, it's likely still considerably easier than making one computer that absolutely will never crash. Most people find it acceptable if their desktop computer crashes once a year; certainly few users would be willing to pay 10x the price to reduce that to one crash every two years. Similarly, modern operating systems are not designed to be absolutely stable, only stable enough, just like Windows 98 was in its day. Our definition of "stable enough" has shifted considerably in 20 years, but the basic premise of trading reliability for cost, complexity, and/or speed still applies. The user you are addressing has obviously chosen to trade some reliability for speed, and that is his prerogative.

[HavingPhun]

4x4GB of DDR3/2133 is going to run around $160-$225.  Which is not that bad and seems to be a standard clock frequency.  DDR3/2400 is a bit more expensive (5-15%).

Except that a lot of CPUs/motherboards only support DDR3/1600, unless you jump through some extra hoops.  Anyone have a list of MB/CPU combos that support DDR3/2400 speeds?

It's strange, two years ago when I built my pc, I bought 4x4gb of ram and it was $30. Why have the prices skyrocketed?

[wierd]

You are misunderstanding what Quietust was getting at.

In the win9x days, the CPU was switching in and out of protected mode, having to juggle a bunch of memory space alignments while processes did that, with processes doing things with memory and hardware that the kernel was not supervising. This led to the inevitable situation where process A does something with process B's resources while process B isn't looking, then when process B tries to use that resource, it cant, and it panics. BOOM, Access violation BSOD.

To resolve this problem, Microsoft totally redesigned the way they handled process resource allocation, and used the windows NT architectural model. This model lives 100% in protected mode, with the kernel being king of the mountain. (No exceptions!)  All resource accesses and allocations MUST go through the kernel, which prevents the previously cited craziness from happening. (It is also why many older 9x software had difficulty with NT flavor OSes back in the day. This was especially true of device drivers, which were the primary culprits for BSODs.) Because the kernel is running the show for everything involving resource use, it is able to trap exceptions when they do happen, and is able to pause or halt processes that are misbehaving gracefully. This is why when a program bombs out in NT flavor windows environments, it does not make the whole system crazy like it used to do in the 9x days.  As a consequence of this, now BSODs only happen when there is a severe fault.

THAT is what Quietust was saying.

If you are experiencing a BSOD, it means that a severe, and unrecoverable access error has occurred and that the system has elected to halt itself rather than risk data corruption on permanent storage by allowing the system to continue. Currently, the most likely cause of a BSOD on an NT flavor kernel is going to be a software programming issue with the disk storage drivers. (SATA drivers especially in my experience.) However, it can also be a memory access error.

Incorrect RAS/CAS timings for your chips can cause data to be written incorrectly to memory cells, making the stored data invalid-- the system relies on that data being valid for the system to operate. When invalid data is read from a valid address, it makes the system behave in unpredictable fashions, which is why when modern kernels detect this, they freak out and halt. (Full disclosure: There are mechanisms intended to correct for small memory inconsistencies, like ECC, which is built into the memory chip itself which attempts to correct incorrectly written data using a simple algorithm. However, ECC is not a magic bullet. Driving memory too fast can and will overwhelm such corrective technologies, and the system WILL be unstable!)

Most modern systems are able to probe the memory chip's I2C bus eeprom to get the manufacturer recommended timing data. This is a tiny eeprom about the size of 2 grains of rice, stuck in one of the corners of the DIMM module.

Spoiler: For the curious, here's an image highlighting such an I2C eeprom (click to show/hide)

This little chip is what tells the system what size the memory module is, what the RAS/CAS timings are, and other pertinent information for proper access. Most gaming systems allow you to override these manufacturer settings, and implement new timings. Some chips can handle different timings. Some cannot.  It's a bit like OCing-- Including the increased risk of system instability.

In short-- what Quietust was getting at, is that with modern NT flavor kernels, YOU DONT GET BSODS UNLESS SOMETHING REALLY BAD HAPPENED.   Memory not storing data reliably, is something very bad happening!


 

[Max™]

Yeah, to add to that, I'm using an utterly unsupportable OS (Arch, for which support amounts to "read the manual, have fun!") and the only thing that gives me any sort of instability is tinkering with my ram timing, I can poke at the voltage a bit, I can even alter the CL I think (9-9-9-24 values iirc) a little, but doing that plus changing the uh... crap forgot what it was, I think the options were like T, T1, T2, etc. I didn't mess with them too much because no matter what I tried there I just got a "KERCLICK" *reboot* loop and didn't push much after that.

Besides that, no, haven't had a problem which didn't directly involve my screwing something up, and even the piece of crap emachine downstairs running W7 doesn't BSOD. That's very much an earlier OS issue.

[Loci]

As a consequence of this, now BSODs only happen when there is a severe fault.

THAT is what Quietust was saying.

Whereas bluescreens were a part of life in Windows 95/98/Me, on Windows NT in general (this includes 2000, XP, Vista, 7, 8, 8.1, and beyond) they shouldn't ever happen.

It's a pretty big leap from "severe fault" to "shouldn't ever happen".

In short-- what Quietust was getting at, is that with modern NT flavor kernels, YOU DONT GET BSODS UNLESS SOMETHING REALLY BAD HAPPENED.   Memory not storing data reliably, is something very bad happening!

We seem to have differing opinions on what "something very bad" is. I would call irreparable damage like the computer bursting into flames "something very bad"; an infrequent memory error not so much. Either way, the fact remains that computers occasionally crash. Telling people that it shouldn't ever happen is misleading at best.

[Putnam]

As a consequence of this, now BSODs only happen when there is a severe fault.

THAT is what Quietust was saying.

Whereas bluescreens were a part of life in Windows 95/98/Me, on Windows NT in general (this includes 2000, XP, Vista, 7, 8, 8.1, and beyond) they shouldn't ever happen.

It's a pretty big leap from "severe fault" to "shouldn't ever happen".

In short-- what Quietust was getting at, is that with modern NT flavor kernels, YOU DONT GET BSODS UNLESS SOMETHING REALLY BAD HAPPENED.   Memory not storing data reliably, is something very bad happening!

We seem to have differing opinions on what "something very bad" is. I would call irreparable damage like the computer bursting into flames "something very bad"; an infrequent memory error not so much. Either way, the fact remains that computers occasionally crash. Telling people that it shouldn't ever happen is misleading at best.

I think you're misunderstanding "shouldn't ever happen". Here, Quietust means that a BSOD in Windows NT systems means either a failure in the hardware or a failure in the kernel's communication with hardware, which are both very, very bad things that, yes, shouldn't ever happen. Computers occasionally crash, but a BSOD is indicative of a failing computer. Telling people that it should happen is misleading at best. The only times I have ever seen a BSOD on NT systems, it always meant that the computer is going to be replaced within a few months.

The infrequent memory error is indication that something very bad has already happened.

[zimluura]

This idea can be followed even further. Since pathfinding has to be done for many creatures, CPU threads all operate on the same memory (aka: nearly no extra RAM needed), and the pathfinding of one creature does not interfere with the pathfinding of others (as a first, and probably good enough approximation), it does not sound to unreasonable to me, to have several pathfinding-threads running.

I was trying to think of a good way to do it the other day.  As always, when discussing this kind of thing I've got to make lots of (hopefully educated) guesses, so I could be wrong.

I assume that DF sequentially goes through the creature list processing the first creature's pathfinding (from what i heard it's the A* method) and then moving that creature before going on to the next.  This way each creature finds a path to its destination exactly before it moves.  If instead, the first loop processed long paths (more than >15 squares away) and cached the path data in a separate space in ram for each creature.  That would be easy to do concurrently.  Then after the 2+ cores do that; each creature gets a sequential pass for close range (<=15) goal seeking and dynamic obstacle avoidance.  That seems like it would do a pretty good job to use other cores for path finding.  The second pass is so you don't get two dwarves constantly stepping into each other's way in a hallway (though that does sometimes happen IRL).  This seems like it would make the game faster even if there were only 1 thread because the long range pathfinding could be called less frequently.  Again so so much of the applicability of this depends on source-knowledge we don't have, so it's mostly an interesting academic discussion.

Parallelizing calculations on such a low level might be the most work intensive way of using multi-core CPUs, but it's in my opinion the "proper" way.

When you said “low level” there it made me think that somehow one might be able to multi-thread the A* pathfinding algorithm.  If that could be done efficiently it could be a drop in replacement.  At the risk of being even more off-topic... Anyone here have experience doing anything like that?

[Loci]

I think you're misunderstanding "shouldn't ever happen". Here, Quietust means that a BSOD in Windows NT systems means either a failure in the hardware or a failure in the kernel's communication with hardware, which are both very, very bad things that, yes, shouldn't ever happen. Computers occasionally crash, but a BSOD is indicative of a failing computer. Telling people that it should happen is misleading at best. The only times I have ever seen a BSOD on NT systems, it always meant that the computer is going to be replaced within a few months.

The infrequent memory error is indication that something very bad has already happened.

Then you've never cleaned a virus, fixed a corrupted registry, or rolled back a poorly-coded driver? The day is yet young; ask your friends and family if their computer has *ever* crashed so you too can experience troubleshooting a crash on functional hardware. I have fixed a number of computers, and I can say with certainty that blue screens are not solely a hardware problem. Indeed, Microsoft's own documentation says that "These errors can be caused by both hardware and software issues".

Upthread, the BSOD were likely caused by aggressive memory timings. That is not indicative of a "failing computer", it's just indicative of running the memory beyond absolute stability.

[wierd]

Why not just enumerate the number of child objects in the creature vector, store a counter value for this number, then begin multiple parallel pathfinding operations with start/stop bounds on the vector based on the number of CPUs you can run threads on?  Since each thread is working with a discrete chunk of the creature vector, they shouldn't (in a perfect world anyway) walk on each other's data structures.

EG, you have a dual core system, and a 10mb creature vector needing updated pathing.  Thread A takes the top 5mb of the vector, thread B takes the bottom 5mb of the vector, with alignment of memory addresses based on whole child object structure granularity. (Rather than 5mb, it would actually be "exactly half of the objects to be evaluated") It would need some glue to handle uneven division, but that's a trivial thing.

Main thread's job is to keep the number of items in the vector recorded in the counter, spawn the pathfinding threads, then wait for all data to be collected from those threads before continuing.

This would only give at best a linear performance increase with number of added cores, but would still make use of simple parallelism.

DF would STILL have the nasty memory-bound constraints issue though.

[wuphonsreach]

It's strange, two years ago when I built my pc, I bought 4x4gb of ram and it was $30. Why have the prices skyrocketed?

You may have been purchasing much lower speed DDR3? I've done some pricing this week and 4x8GB DDR3/2400 is $400 for the good stuff.

The main thing to look for is a motherboard that supports "XMS", those motherboards support the higher memory speeds above DDR3/1600.  The memory chip also needs to have XMS, but most do.

I'm debating either the ASRock Z97 Extreme9 or Asus Z97-WS motherboard.  Both are about $300, support the Intel Core i7-4790K Haswell ($350), and support the higher memory speeds.  A rough estimate is that single-core performance would be about 30% better then my AMD FX-8350, but the DDR3/2400 vs the DDR3/1600 that I have install might get me another 20%.

[zimluura]

Why not just enumerate the number of child objects in the creature vector, store a counter value for this number, then begin multiple parallel pathfinding operations with start/stop bounds on the vector based on the number of CPUs you can run threads on?

My suggestion would be like that, but assumes that, in its current form, the creature vector move loop looks like:
*  Creature 1: calculate path, do move along path, process physics for move.
*  Creature 2: calculate path (considering the world changes due to creature 1's move), do move along path, process physics for move.
*  Creature 3: calculate path (considering world changes from 1 & 2) ...

If things actually _are_ that way, then you can't guarantee that a creature won't move into the same spot as a concurrently moving creature.

I was trying to describe something like:
1) Use all available cores to process general path (for terrain only) for each creature concurrently (exactly like your method) and save the path into a 3d boolean array (spaces he can walk and spaces he can't) for said creature.  Wait until the paths have been found for all creatures.

2) Loop through creature vector sequentially:
Apply same old pathfinding to then move him slightly further along the pre-calculated (and much smaller and closer) path in the same as it does now.

Again, this is all based on my assumptions about how it works at the moment.

Since each thread is working with a discrete chunk of the creature vector, they shouldn't (in a perfect world anyway) walk on each other's data structures.

For 2+ threads churning one creature's data, I would think to just make sure the vector doesn't change size until in-between full passes.  Have a queue for deletion(dead?) and one for addition (migrants?).  Or were you talking about something different?

[perkel]

I think with DF people are just confused and look for common problems either GPU or CPU.
IT is not really a CPU or GPU problem it is RAM problem. Game with so much data flung around simply needs super fast memory so it can read and write fast enough to cope with what is happening on screen.

So with DDR4 we should be happy as it will improve a lot speed. Especually stacked one that will eventually come in near future.