Wikipedia:Reference desk/Archives/Computing/2012 September 26

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 26

Particle Simulation in Parallel using MPI

I am not very sophisticated in programming skills and am teaching myself MPI. So while trying to program a toy particle simulation, I see a problem but not its solution hence I appeal to the computing reference desk. Basically, I have a 2D square grid and a velocity vector field with known values on the grid points. For values inside the cells, I am just using bilinear interpolation and the field stays constant for all time. I want to drop a bunch of particles in this field and then follow their trajectory over time. The particles are also non-interacting so this is an embarassingly parallelizable problem. Very easy problem in serial and my goal is to parallelize this so that I can use a large/dense grid and/or a large number of particles eventually. I see two obvious/naive ways to parallelize this and one of them is I do a domain decomposition (slab-wise) where each rank gets a row of the domain and the rank keeps track of the particles in its domain. When they leave that slab, the rank communicates with the next rank and the next rank takes over that particle. I thought a simple MPI-send/receive would work but then I realized that this wouldn't work. Assuming there are only two ranks and a particle leaves rank 1, rank 1 can MPI-send its trajectory but how would rank 2 know to initiate MPI-recieve? On the other hand if rank 2 is MPI-receiving but rank isn't MPI-sending then wouldn't rank 2 just sit there and wait for something to be received? I need something like where rank 1 and 2 both work independently and just keep on simulating not sending or receiving UNTIL there is a particle which leaves a rank. Then and ONLY then, should an MPI-send and receive be initiated by both, the particle is passed from rank 1 to rank 2, and both ranks resume. Is there anothe MPI function perhaps which might do the trick? Thanks.161.98.13.100 (talk) 02:04, 26 September 2012 (UTC)

This approach seems wrong to me. Instead, how about if each processor handles a particle ? Just pass the grid of velocity vectors in, along with the particle, and have that process run the simulation on that particle, until it leaves the grid. The only interaction required with any other process is to display the particle. If this isn't a real-time simulation, you can just have the process output the trail the particle takes (at whatever resolution you need), when the process ends. StuRat (talk) 02:21, 26 September 2012 (UTC)

OP here, this is exactly the other approach I thought of. The thing is I kind of want to do both and compare their runtimes and scaling to see how they do. There are advantages and disadvantages to both. One physical check that I must do is (perhaps at every time step) is make sure that no two particles occupy the same physical space coordinates. With the first method, each rank just checks its own grid. With the second method, each rank checks all of its own particle AND THEN the location of each particle must be broadcasted to check against all other particles in all other ranks. Seems to me an awful communication overhead, unless someone can suggest something clever for this problem too here.174.16.229.18 (talk) 03:54, 26 September 2012 (UTC)

OK, that new requirement does rather change things. I thought they didn't interact with each other. Is there a minimum clearance distance between two particles ? What happens if a particle collision is detected ? StuRat (talk) 04:07, 26 September 2012 (UTC)

It may be that this just isn't a program which is suitable for parallel processing, due to all the inter-process communication which would be required. You might just stick with your serial approach for the "particle engine", and then, after each time step, launch a process to render that frame, passing in the current positions of each particle. A final process would then stitch the frames together into a video. StuRat (talk) 04:22, 26 September 2012 (UTC)

BTW, we do have an article on Message Passing Interface. Have you already read that ? StuRat (talk) 04:24, 26 September 2012 (UTC)

Here is a simple implementation of a similar problem [[1]]. They send and receive after every computation step, which is probably introducing a ton of overhead but still lets you get an idea of how to implement this sort of thing. With the proper interconnet and a computation step that takes a bit longer, this approach works fine. If you were simulating a much larger area so each node has a decent amount of work to do, then this would probably do a very good job.

The problem with triggering MPI send/receives (it is possible with multithreaded code) only when needed is that you run into race conditions. The communication is usually slower than the computation, so if node A sends a particle to node B at time step 3, then B should receive it in time ofr time step 4. If there isn't anything synchronizing your systems (like the send/receive pair every step), then B could be on to time step 5 or 6 by the time the message about the new particle gets there. 209.131.76.183 (talk) 11:44, 26 September 2012 (UTC)

Does that example handle collision detection ? That seems to be the main problem with parallelizing this program. StuRat (talk) 18:30, 26 September 2012 (UTC)

One good point from that example is that, if broken up into zones, you want to minimize the perimeter in order to minimize the number of particles crossing the perimeter, and therefore the amount of inter-process communication required. So, we want roughly square zones, not long rectangles. StuRat (talk) 21:20, 26 September 2012 (UTC)

You do need to communicate with other nodes during every time step. Otherwise, node 1 will not know that node 2 is sending a particle over. What you can do to minimize communication overhead is have a two-step non-blocking send/receive approach, where you figure out how many particles need to be sent/received from every other node, and then if you have a non-zero number of particles, begin the actual particle transfer. It would look like this:

1. Post a non-blocking receive (MPI_IRECV) for one integer
2. Figure out how many particles you want to send to other nodes
3. Start a non-blocking send (MPI_ISEND) with the number of particles you will send to every other processor (you can do something like MPI_SCATTER if you want, but I don't remember off the top of my head whether you have non-blocking scatter/gather operations)
4. Use MPI_WAITALL to figure out when you have gotten everything
5. At this point, you will receive the number of particles your node will receive from all the other nodes. Generate your particle receive buffers and post non-blocking receives (MPI_IRECV) of different sizes for all of them.
6. Generate your particle send buffers
7. Start non-blocking sends (MPI_ISEND) for all the send buffers.
8. Use MPI_WAITALL to figure out when you have gotten everything, and when it is safe to free memory allocations.

Using non-blocking sends and receives is critical here, as this allows you to do some computational work while communications finish, increasing the scalability of your code. Titoxd^{(?!? - cool stuff)} 18:55, 26 September 2012 (UTC)

OP here, thanks for all the good ideas guys. I was afraid of this sending and receiving on every time step. I guess I was looking for a non-blocking send and receive which (now I know) does exist in MPI. As for StuRat's comment about minimizing the perimeter, I figured that if I use a square for each rank, then each rank will communicate with its four neighbors (or maybe eight if I let particles go directly to a corner through a gridpoint) and then I would need a cartesian topology and what not. I want to use slabs so that each rank then only has two neighbors. The boundary conditions are periodic so using horizontal slabs, if a particle hits the left/right wall it just wraps around and stays on the same rank. If it hits the top/bottom wall then it just moves to the appropriate adjacent rank. In addition, each rank will have to communicate ONLY with its two neighbors because the particles cannot jump directly from rank 1 to rank 3 skipping over rank 2. The time steps are small enough to ensure that the change in position stays small enough. So basically, use the non-blocking send and receive after every time step. If there is a particle to send, then send it. Otherwise send zero or a null pointer or something, right? And then use MPI_WAITALL to sync all the ranks? But if I am using MPI_WAITALL to sync the ranks, then why not just use the blocking send/receive? I don't think I want computation to go on while communication is being done. Otherwise some particles will be "behind" others in time. In this example, the field is constant in time but later on I will be using fields changing in time. And even if the field stays constant, some particles will have gone through fewer time steps and their trajectories will be incomplete.128.138.65.200 (talk) 23:21, 26 September 2012 (UTC)

Question for you: Are you trying to find the most efficient way to write this program, so long as it uses parallel processing, or regardless of what methods it uses ? In the later case, I think that my suggestion of leaving the particle engine serial and only using parallel processing for generating graphics frames would be the way to go, as the inter-process communication requirements are severely reduced, in one direction only, and no process needs to wait while communicating (except perhaps the process which stitches the frames together into a video). StuRat (talk) 23:35, 26 September 2012 (UTC)

If you have time-dependent fields, then yes, you will need to sync every timestep. The computation you are doing after the non-blocking receive posts is communication-related, so you will ameliorate some of the wasted time that you would spend on non-blocking sends. Titoxd^{(?!? - cool stuff)} 04:05, 27 September 2012 (UTC)

Encryption of RFID chips

What about an RFID chip would be encrypted? Is this unnecessary if the RFID signal only transmits a serial number? Wouldn't an encrypted RFID chip still be possible to copy? --Melab±1 ☎ 01:58, 26 September 2012 (UTC)

If it only contains a serial number, then nothing secret is actually on the RFID chip, that's all actually kept in the database. So, provided you keep the database secure, that info will not get out. Therefore, encryption of a serial number does seem unnecessary, yes. However, some serial numbers, like the US Social Security number, are themselves sensitive data. StuRat (talk) 02:12, 26 September 2012 (UTC)

The big security concern with RFID is this one:

However, the encryption on UK chips was broken in under 48 hours

Hcobb (talk) 06:23, 26 September 2012 (UTC)

Define "encrypted". The whole point of an RFID is to transmit something. In a good secure system that'd be signed in some way (in which case you need to worry about putting a key in a tamper resistant form, which is quite hard), and the better solution is to do some sort of handshake algorithm. But you can't just call anything, whether it's an RFID, an ATM card, or a SIM card, "encrypted" without describing which threat you're trying to avoid.

RFID cards could be storage devices, in which case encrypting them would be useful, but that doesn't seem to be their primary use, so maybe if you could be more specific about what kind of application you're thinking about, or even better, threat, we could answer more intelligently. Shadowjams (talk) 07:11, 26 September 2012 (UTC)

Contactless card keys (where you tap your card against a sensor in order to unlock a building entrance, etc.) are a very common RFID application. To prevent straightforward copying and replay attacks, the RFID has to have a cryptographic secret, and participate in a challenge-response protocol with the card reader. 69.228.171.70 (talk) 07:36, 26 September 2012 (UTC)

nvidia 9800 GT 1024 on Windows 7 crashes

Hi, My brother has recently upgraded his computer from Windows xp to 7. After it was upgraded the computer has randomly crashed. We have replaced the display card ,and since the replacement it has been working. In the Windows xp the display card original worked. The card is nvidia 9800 GT 1024, the Windows 7 is 32bit. So does anyone know what should we do to install successfully the original card? Exx8 (talk) 09:12, 26 September 2012 (UTC)

I would guess that the software driver for that card isn't working under Windows 7. You could try downloading a replacement, but if it's still defective, you might have to wait until they fix the bug in the driver.

Another possibility is that your computer runs hotter under Windows 7, and this is hot enough to make the graphics card lock up. You can diagnose if this is the problem by removing the case and pointing a fan at the guts. If that fixes it, then a permanent solution might be a bigger case fan. StuRat (talk) 18:20, 26 September 2012 (UTC)

You could try downloading an older driver from the nvidia website. I've seen later drivers introduce bugs, and I suspect they don't do much backward (you're at least an nvidia generation behind) compatibility testing with newer drivers. Sandman30s (talk) 10:29, 27 September 2012 (UTC)

Windows 7 Title Bar Grabbing with Excel

With Windows 7 you can take a non-maximized window by the title bar and drag it up to the top of the screen to maximize the window, or grab a maximized window by the title bar and pull it down, at which point it becomes a non-maximized window. But, at least for me, with Excel, you can take a non-maximized window and maximize it by dragging it to the top, but you can not pull down a maximized window by the title bar. Why is this? If my premise is wrong, and there is evidence that others can pull maximized Excel windows down by the title bar, please show me proof. 20.137.18.53 (talk) 17:53, 26 September 2012 (UTC)

Seems it is a known bug.[2] Thincat (talk) 23:32, 26 September 2012 (UTC)

It works for me with Excel Starter edition running Windows 7 Home edition. 67.163.109.173 (talk) 22:05, 1 October 2012 (UTC)

Third party incompatibilities

I heard that some companies use "methods" in order to make third party accessories harder to develop or even to fail. Is this true, and if so, how do they do this? Two examples I heard about:

1. printer ink cartridges of third party manufacturers which are not recognized after a certain amount of time
2. camera lenses/flashes of third party manufacturers which might work well with today's camera bodies but might have less functionality with future bodies (while even old orginal lenses/flashes have full functionality today and in the future). bamse (talk) 19:42, 26 September 2012 (UTC)

The simplest way is to not publish precise specifications for your product, so that third parties are forced to guess at what their accessories will need to do in order to work. This works even better if the specifications are baroque and bizarre. Looie496 (talk) 20:22, 26 September 2012 (UTC)

Thanks for the reply, but are there more "active methods" that are being or could be used? bamse (talk) 20:46, 26 September 2012 (UTC)

The most active method I can think of allegedly occurred in when Microsoft removed API functions that Novell depended on for Wordperfect 7 (iirc). Legal action on that, started in 2004 [3], is still going on to this day [4]. --Tagishsimon (talk) 20:57, 26 September 2012 (UTC)

Another good example AARD code 92.233.64.26 (talk) 21:03, 26 September 2012 (UTC)

In the case of printer ink cartridges, I thought they went right up to having a coded "license" on the cartridges, and the printer will refuse to use any cartridge without the proper license. They presumably could then sue anyone producing a cartridge using a counterfeit license. StuRat (talk) 21:16, 26 September 2012 (UTC)

Yes, that's true. See Lexmark Int'l v. Static Control Components. -- BenRG (talk) 00:24, 27 September 2012 (UTC)

Batteries. Makers of laptops, mobile phones and other gadgets design a custom battery for each model. They may differ in a minor way in shape or position of electrodes just to make them incompatible, which means you can't buy them at a local shop except an official one that agrees to charge an inflated markeup, and they hope you can't buy them from an independent maker. Jim.henderson (talk) 00:11, 27 September 2012 (UTC)

This happens all the time and it's hard to know where to begin. One example is the mechanisms on many game consoles to prevent unauthorized games from running, going back at least as far as the NES lockout chip. Another example is Mac OS which is designed to run only on Apple Macintoshes, which can't be made by third parties. Another example is Apple's monopoly on iOS apps and Microsoft's apparent upcoming monopoly on Metro apps. That's just off the top of my head. These are enforced by some combination of intellectual property rights, cryptography, and simple obscurity. -- BenRG (talk) 00:24, 27 September 2012 (UTC)

Yes, some people still want to use videocassettes

My wife and I want to buy an HDTV with all the bells and whistles PLUS the ability to connect to a videocassette recorder. Can that be done? Thanks, --Halcatalyst (talk) 23:52, 26 September 2012 (UTC)

A VCR typically emits a signal in the prevailing analog TV format, where the physical connection is an RF connector, a composite connector, an S-video connector, or a penitel SCART connector. So you need to check whether the HDTV you're considering has such an input, and that the VCR you're planning on using it with has the same kind of output. -- Finlay McWalterჷTalk 23:56, 26 September 2012 (UTC)

By way of example, I just checked the first HDTV I found on Sony's UK site. It still has an analog decoder for PAL, and inputs on SCART, Composite, Component, and the usual UK coaxial RF connectors. -- Finlay McWalterჷTalk 00:05, 27 September 2012 (UTC)

The other option, if you have an HDTV without an appropriate connector that you want, is to purchase a separate box which converts the RF/composite/VGA/etc. output of the VCR into an HDMI input for the HDTV. (These can typically be purchased for around US$50, though a quick check of the Amazon UK site shows ones of around £50 - though cheaper ones might be found.) The separate box might not make sense if the TV is solely being used for your VCR, but if VCR use is only occasional, it might be the better choice, as it allows you to get whatever HDTV you want. -- 205.175.124.30 (talk) 02:22, 27 September 2012 (UTC)

Note, however, that a VCR won't have a widescreen output. So, that means your HDTV will present it with black bars on the sides, stretch it, or some combo of the two. Also, it won't have HD resolution, so, on a large TV, it might look blurry. StuRat (talk) 00:04, 27 September 2012 (UTC)