CS 312 (W'07, T Th sections)

I tried running some of the test files on one of the computers in the lab, and when I tried to run some of the more detailed files (the ones with the spheres), the computer rebooted without warning. This happened twice (on different files). Any ideas on what's going on?

Peter,

My guess would be that the video card on the lab machine is not sufficient for the task of dealing with our 3d models. We tested the project in the lab machines, but didn't see this.
Could you give us the file names for the files on which the computer reset? Can you generate and view random graphs by clicking on the "random" button?

We are looking into this.

Mik.e

I'm not in the lab. When I run the StudentProject in debug mode in my VS2005, I get this error. But when I just execute it, it seems fine. Does anyone else get this, and anyone know a fix? It precludes my using debug mode.

LoaderLock was detected
Message: DLL 'C:\WINDOWS\assembly\GAC\Microsoft.DirectX.Direct3DX\1.0.2908.0__31bf3856ad364e35\Microsoft.DirectX.Direct3DX.dll' is attempting managed execution inside OS Loader lock. Do not attempt to run managed code inside a DllMain or image initialization function since doing so can cause the application to hang.

Andrew,

It is a feature not a bug :)

The project we distributed has loader lock detection disabled. We believe that it will be disabled for everyone using that project. It works on my install of VS 2005 on my laptop. In the interest of making sure that our belief is correct, are you using your own project or a non-standard installation of VS 2005?

Anyway, to disable it, the steps are a close approximation of...
In VS 2005 with an open project select ... Debug | Exceptions | Managed debug assistance | Option to avoid loader lock | uncheck.

I don't have VS running at the moment, but Jeremy the TA says that's the gist of it.

Per Peter's loading problem:
I checked on Rowlf in the muppets lab and every single file opened fine for me, and I could move the images around and stuff, so I'm not sure what the problem is.

It would help a lot if you could let us know exactly which files and on what computers the error is occurring.

PS During the help session we did have a few reboots after playing with the program for a while, but none upon loading an image.

I imagine that it probably has something to do with the fact that all the Windows XP computers have the default Microsoft drivers instead of the Nvidia drivers, but I'm not sure.

My work computer, which does have the vendor-provided video drivers installed, also rebooted when I was recoloring the vertices and rotating the image at the same time. At other times I get exceptions rather than reboots that say something about protected memory being written to and causing corrupted memory.

It's not a good feeling to imagine finishing this project when it reboots this much during development.

Andrew,

Tell me a little more about the machine you have at work. Doing graphics in hardware or software?

Crashing on big files or little ones or both?
What is the program doing approximately when it crashes? What if you turn off updating from the solver class?

I am asking because we can't duplicate the errors in our lab (otherwise we wouldn't have released it of course).

If you get sick of the directX stuff (which I can't blame you for), you can just turn it off and do everything through a terminal, by the way.

Mike.

I should also mention that we think this blue screen thing might be a memory access violation caused by two threads reading and writing the same data simultaneously. We've got some code in which we've added more locking to avoid simultaneous reads and writes. I am testing it now (to make sure we didn't introduce new errors). We can't say if it fixes the errors reported by others, but it may.

Mike.

I found that by remoting into my development computer through RDP, my computer doesn't reboot, but instead just throws an exception. These details may be useful to you in debugging the project distribution:

System.Exception: Invalid item in array vertices. ---> System.AccessViolationException: Attempted to read or write protected memory. This is often an indication that other memory is corrupt.
at Microsoft.DirectX.Direct3D.VertexBuffer.SetData(Object data, Int32 lockAtOffset, LockFlags flags)
at ArticulationPoints.UserInterface.UpdatePointVertexBuffer(VertexBuffer vb, ArrayList al) in C:\\wc\\ArticulationPoints\\ArticulationPoints\\UserInterface.cs:line 393
--- End of inner exception stack trace ---
at ArticulationPoints.UserInterface.UpdatePointVertexBuffer(VertexBuffer vb, ArrayList al) in C:\\wc\\ArticulationPoints\\ArticulationPoints\\UserInterface.cs:line 397
at ArticulationPoints.UserInterface.InitializeImage() in C:\\wc\\ArticulationPoints\\ArticulationPoints\\UserInterface.cs:line 521

I'm struggling to implement 2(b) of the 9.3.1 algorithm using a stack data structure, anybody gotten here or hitting it from a clever angle?

Andrew,

Thanks for the error information. That is very helpful. At what point in the execution of the program did you get the exception. Was it while loading a file (if so which one)? While doing the BFS search? While just sitting there and looking at the pretty graph?

Mike.

Greg,

The main challenge in 2b is checking the existence of edges in G and T. You might add a pair of hashtables to your implementation. One to store edges in T and one to store edges in G.

Does that answer seem related to your question? (I am not sure I understood the question).

Mik.e

Dr. Jones-

Yeah, the double hashtable idea is a good one and should give me something to go on...

Dr. Jones,

I think the exception trace that I included was from watching the bfs in run mode. I may have been dragging to get different angles at the same time that bfs was in progress. I can't remember for sure.

I was preparing to post a question, but as I finished the question, I realized the answer. I leave it here anyway for anyone else's benefit:

So I'm done with the articulation point algorithm, where I have steps 1 and 2 separate.
Step 1: Do a depth-first search to assign prenum's to all nodes and to discover the spanning tree that I will later use for step 2.
Step 2: Do a post-order traversal of the spanning tree to calculate highest[x] values for each node.

But now as I'm preparing to modify the algorithm to combine 1 and 2, I see that I would not expect the algorithm to run in 1/2 the time. I'm wondering if I understand it right. See, the prenum's have to be done as you drill down from the root through the whole graph. The highest[x] values have to be calculated after the prenum's are all set. Therefore, in a single depth-first traversal, you set prenum's "on the way in" and set highest's "on the way back out" of recursion. BUT you're doing work 2n times. n times on the way in, and n times on the way out. Now, if I did a depth first search (n steps) and then did a post-order traversal as a separate step (n steps), I still have 2n work. So, while I can see a way to implement it with the two steps combined, I don't think it will be any faster.

Ok, so here's my mistake in my reasoning that I just now realize: the post-order traversal requires 2n work itself (n to get down to the bottom, and n to work itself back up). So by combining steps 1 and 2, we actually reduce work from 3n to 2n. We reduce work therefore approximately 1/3 (rather than the 1/2 given in the Word document that came with the distribution). I think.

So the circle-9v-0ap.x3d file will not load. I get the below error message. So, I'm not sure what to do about my write-up, since a graph with no articulation points is a required piece of it, and this was the only file with 0 ap's.

loaded graph with +0 vertices and 0 edges
Error in the application.

For the "normal" implementation, I used an iterative algorithm, which worked fine. The "on-the-fly" algorithm is much faster, but uses recursion. On a 10K+ node graph, that's 10,000+ recursions, and a StackOverflowException inevitably results.

Apparently, the C# compiler doesn't offer a switch to control the size of the program's stack. BUT there is a way to do it. I think many of you will find this blog useful.

Here's a little bit more about avoiding that StackOverflowException. The blog link that I provided in my last post wasn't very helpful in actually building the batch file that would increase the stack size of your program at build time. Here is how to do it:

1. Under project properties, select the Build Events tab.
2. In the "Post-build event command line" box, enter this as all one line:
"$(ProjectDir)bigstack.bat" "$(DevEnvDir)..\..\VC\" "$(TargetPath)"
3. Now write a batch file, and save it in your project directory (the one with StudentProject.csproj in it). The next 3 lines is the contents of the batch file:

@echo off
call %1vcvarsall.bat
editbin /stack:3000000 %2

This will increase the stack size of your StudentProject.exe program. But the program that runs in VS' debugger (StudentProject.vshost.exe) is not altered, so your debugging experience will still have the limited stack size. You'll have to explicitly run the StudentProject.exe program to get the bigger stack size.

how am i supposed to do the report (which requires some test cases to run over 5 seconds) when all of the test cases run in a fraction of a second and the only one that takes longer causes a stack overflow??!!

StephenCondie,

Generate larger random graphs. See MAXRANDOMGRAPHSIZE on about line 64 of Visualizer.cs Generating good sample problems is a part of the empircal analysis of algorithms and this will give you a small taste of what that's like.

Andrew,

Could I trouble you to try the following:
change every instance of LockFlags.Discard in UserInterface.cs to LockFlags.NoSystemLock. That should hurt performance, but may give us the locking we need to avoid simultaneous writes and reads

I count 7 articulation points on grids-17v-1ap.x3d, not just one. Any of the verticies connected by only one line can be separated from the graph by removing the vertex it is connected to. The algorithm seems to support that. IDON'TKNOW.

Nathan,

That's right. What happened is that the x3d exporter in blender or the x3d reader in our application (you make the call) doesn't include the missing lines that would both make the grids complete and allow only 1 articulation point.

Also, note that grids-41v-4ap.x3d has more than 4 articuation points as well.

FYI, I had to set MAXRANDOMGRAPHSIZE to 20,000 to get my "normal" algorithm to take more than 5 seconds. I hope that's all that's necessary.

NOW, even with MAXRANDOMGRAPHSIZE set to 1, there are always a minimum of 11 vertices to the random graphs (for some reason), and I can't seem to generate one with 0 APs. So, how can we finish our write-up when the one given graph without APs won't load, and we can't randomly generate one? Ideas?

I installed Blender and followed the directions in the Word document to create a simple graph with a circle, with 31 vertices. There are no articulation points (goal being to prepare for the write-up). But an exported x3d file from this won't load in the program we are using. I'm at a loss of what to do. I think I followed the directions.

Andrew,

You'll probably want to tweak the random graph generator to make graphs that do not have articulation points. This can be done by modifying CreateRandomSubgraph on about line 136 of Visualizer.cs The tool chain from blender to x3d is pretty brittle.

I've tried modifying the CreateRandomSubgraph function for 0 art. points but keep getting runtime errors when I try to generate random graphs. Is there anything specific I should be doing? Any help is appreciated. Once I get this part done I'll be done with the project.

I made a created a x3d file with no articulation points. You can download it here.

It is true that the x3d files generated by Blender do not load in the project. The files generated by Blender have to be tweaked first. Later, if I have time, I'll look into changing the loading code so that it accepts either version.

Thanks Mortlath...

Dkendall... All I did to make 0 articulation point graphs was modift the one line in the Visualizer.cs file so that instead of a random number of articulation points, it makes 0... The random graph generator is actually really cool, I can't imagine it was easy to make...

Excellent - I see now - thanks for the file and the help.

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)

URL:
Remember me? YesNo

Comments: