COMP 3000 Essay 2 2010 Question 6 - Revision history

Soma: Protected "COMP 3000 Essay 2 2010 Question 6" ([edit=sysop] (indefinite) [move=sysop] (indefinite))

2010-12-03T19:44:53Z

Protected "COMP 3000 Essay 2 2010 Question 6" ([edit=sysop] (indefinite) [move=sysop] (indefinite))

← Older revision	Revision as of 19:44, 3 December 2010
(No difference)

Achamney: /* References */

2010-12-03T06:38:38Z

References

← Older revision		Revision as of 06:38, 3 December 2010
Line 89:		Line 89:
	=References=		=References=
	[1] Erickson, Musuvathi, Burchhardt, Olynyk,<i> Effective Data-Race Detection for the Kernel</i>, Microsoft Research, 2010.[http://www.usenix.org/events/osdi10/tech/full_papers/Erickson.pdf PDF]		[1] Erickson, Musuvathi, Burchhardt, Olynyk,<i> Effective Data-Race Detection for the Kernel</i>, Microsoft Research, 2010.[http://www.usenix.org/events/osdi10/tech/full_papers/Erickson.pdf PDF]
			<br>
			<b>Contribution</b>
			<br>
			[1] Stefan Savage, Michael Burrows, Greg Nelson, and Patrick Sobalvarro, "Eraser: A Dynamic Data Race Detector for Multithreaded Programs," ACM Transactions on Computer Systems, vol. 15, no. 4, pp. 391-411, 1997.<br>
			[2] Yuan Yu, Tom Rodeheffer, and Wei Chen, "RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking," in Symposium on Operating System Principles (SOSP), 2005, pp. 221-234.<br>
			[3] Michael D Bond, Katherine E Coons, and Kathryn S McKinley, "PACER: Proportional Detection of Data Races," in Programming Languages Design and Implementation (PLDI), 2010.<br>
			[4] Daniel Marino, Madanlal Musuvathi, and Satish Narayanasami, "LiteRace: Effective Sampling for Lightweight Data-Race Detection," in Programming Language Design and Implementation, 2009, pp. 134-143.<br>
			[5] E Pozniansky and A Schuster, "MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs," Concurrency and Computation: ractice and Experience, vol. 19, no. 3, pp. 327-340, 2007.<br>

Achamney: /* Contribution */

2010-12-03T06:33:39Z

Contribution

Nshires: /* Data Collider: */

2010-12-02T23:00:19Z

Data Collider:

← Older revision		Revision as of 23:00, 2 December 2010
Line 83:		Line 83:
	===Content===		===Content===
	=====Data Collider:=====		=====Data Collider:=====
	DataCollider seems like a very innovative piece of software. It’s new use of breakpoints inside kernel-space instead of lock-set or happens-before methods in user-mode let it check data race errors in the very kernel itself without producing as much overhead as its old contenders (it even finds data races for overheads less than five percent). One thing to note about DataCollider is that ninety percent of its output to the user is false alarms. This means that after running DataCollider, the user has to sift through all of the gathered ~~data~~ to find the ten percent of data that actually contains real data race errors.[1] The team of creator’s were able to create a to sort through all of the material it collects to only spit out the valuable information, but the creators still found some false alarms in the output . They have noted though that some users like to see the benign reports so that they can make design changes to their programs to make them more portable and scalable and therefore decided not to implement this. Even though DataCollider returns 90% false alarms the projects team have still been able to locate 25 errors in the Windows operating system. Of those 25 errors 12 have already been fixed.[1] This shows that DataCollider is an effective tool in locating data race errors within the kernel effectively enough that they can be corrected.		DataCollider seems like a very innovative piece of software. It’s new use of breakpoints inside kernel-space instead of lock-set or happens-before methods in user-mode let it check data race errors in the very kernel itself without producing as much overhead as its old contenders (it even finds data races for overheads less than five percent). One thing to note about DataCollider is that ninety percent of its output to the user is false alarms. This means that after running DataCollider, the user has to sift through all of the gathered information to find the ten percent of data that actually contains real data race errors.[1] The team of creator’s were able to create a to sort through all of the material it collects to only spit out the valuable information, but the creators still found some false alarms in the output . They have noted though that some users like to see the benign reports so that they can make design changes to their programs to make them more portable and scalable and therefore decided not to implement this. Even though DataCollider returns 90% false alarms the projects team have still been able to locate 25 errors in the Windows operating system. Of those 25 errors 12 have already been fixed.[1] This shows that DataCollider is an effective tool in locating data race errors within the kernel effectively enough that they can be corrected.

	The overhead of any application running is very important to all users. The developers of DataCollider ran various tests to determine the overhead of running DataCollider based on the number of breakpoints. These results were included in the final paper. DataCollider has a low overall base overhead and it is only after 1000 breakpoints a second does the run time overhead increase drastically.[1] This adds to the effectiveness of DataCollider. Having a low overhead is very important to use of an application.		The overhead of any application running is very important to all users. The developers of DataCollider ran various tests to determine the overhead of running DataCollider based on the number of breakpoints. These results were included in the final paper. DataCollider has a low overall base overhead and it is only after 1000 breakpoints a second does the run time overhead increase drastically.[1] This adds to the effectiveness of DataCollider. Having a low overhead is very important to use of an application.

Abondio2: /* Background Concepts */

2010-12-02T14:56:58Z

Background Concepts

← Older revision		Revision as of 14:56, 2 December 2010
Line 11:		Line 11:


	A data race is a potentially catastrophic event which can be alarmingly common in modern concurrent systems. When ~~one thread attempts to read or write on a~~ memory location at the same time ~~that another thread~~ is ~~writing on the same location~~, there exists a potential data race condition. If the race is not handled properly, it could have a wide range of negative consequences. In the best case, there might be ~~data~~ corruption rendering the affected ~~files~~ unreadable ~~and useless~~; this may not be a major problem if there exist archived, non-corrupted versions of the data. In the worst case, a process (possibly even the ~~operating system~~ itself) may freak out and crash, unable to decide what to do about the unexpected input it receives.		A data race is a potentially catastrophic event which can be alarmingly common in modern concurrent systems. When two threads access the same memory location at the same same time, and at least one of those accesses is a write operation, there exists a potential data race condition. If the race is not handled properly, it could have a wide range of negative consequences. In the best case, there might be corruption rendering the affected data unreadable; this may not be a major problem if there exist archived, non-corrupted versions of the data. In the worst case, a process (possibly even the kernel itself) may freak out and crash, unable to decide what to do about the unexpected input it receives.


	Traditional data-race detection programs operate by running an isolated runtime and comparing it with the currently active runtime, to find situations that would have resulted in a data race if the runtimes were not isolated. DataCollider operates by temporarily setting up breakpoints at random memory access instances. If a certain memory access hits a breakpoint, DataCollider springs into action. The breakpoint causes the memory access instruction to be postponed, and so the instruction pretty much goes to sleep until DataCollider has finished its job. The job is like taking a before and after ~~photograph~~ of something; DataCollider records the data stored at the address the instruction was attempting to access, then allows the instruction to execute. Then DataCollider records the data again. If the before and after records do not match, then another thread has tampered with the data at the same time that this instruction was trying to read it; this is precisely the definition of a data race.		Traditional dynamic data-race detection programs operate by running an isolated runtime and comparing it with the currently active runtime, to find situations that would have resulted in a data race if the runtimes were not isolated. DataCollider operates by temporarily setting up breakpoints at random memory access instances. If a certain memory access hits a breakpoint, DataCollider springs into action. The breakpoint causes the memory access instruction to be postponed, and so the instruction pretty much goes to sleep until DataCollider has finished its job. The job is like taking before and after photographs of something; DataCollider records the data stored at the address the instruction was attempting to access, then allows the instruction to execute. Then DataCollider records the data again. If the before and after records do not match, then another thread has tampered with the data at the same time that this instruction was trying to read it; this is precisely the definition of a data race.

Abondio2: /* Background Concepts */

2010-12-02T14:51:23Z

Background Concepts

← Older revision		Revision as of 14:51, 2 December 2010
Line 18:		Line 18:

	Most existing data race detectors use static detection techniques. These involve analysing program source code to determine where simultaneous accesses occur. This method is typically seen as less effective because it produces a warning every time synchronous accesses occur; the program then has to sort out all the false warnings from the legitimate error reports. The problem is that there are no heuristics that can consistently eliminate the false warnings without also eliminating some of the legitimate reports. DataCollider uses a dynamic detection technique, which involves analysing program output and recognizing anomalous data accesses. Dynamic detectors also produce false warnings, but not nearly as often as static detectors.		Most existing data race detectors use static detection techniques. These involve analysing program source code to determine where simultaneous accesses occur. This method is typically seen as less effective because it produces a warning every time synchronous accesses occur; the program then has to sort out all the false warnings from the legitimate error reports. The problem is that there are no heuristics that can consistently eliminate the false warnings without also eliminating some of the legitimate reports. DataCollider uses a dynamic detection technique, which involves analysing program output and recognizing anomalous data accesses. Dynamic detectors also produce false warnings, but not nearly as often as static detectors.

	~~--[[User:Abondio2\|Austin Bondio]] 14:47, 2 December 2010 (UTC)~~

	=Research problem=		=Research problem=

Abondio2: /* Background Concepts */

2010-12-02T14:47:54Z

Background Concepts

← Older revision		Revision as of 14:47, 2 December 2010
Line 9:		Line 9:

	=Background Concepts=		=Background Concepts=
	~~Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.~~


	A data race is a potentially catastrophic event which can be alarmingly common in modern concurrent systems. When one thread attempts to read or write on a memory location at the same time that another thread is writing on the same location, there exists a potential data race condition. If the race is not handled properly, it could have a wide range of negative consequences. In the best case, there might be data corruption rendering the affected files unreadable and useless; this may not be a major problem if there exist archived, non-corrupted versions of the data. In the worst case, a process (possibly even the operating system itself) may freak out and crash, unable to decide what to do about the unexpected input it receives.		A data race is a potentially catastrophic event which can be alarmingly common in modern concurrent systems. When one thread attempts to read or write on a memory location at the same time that another thread is writing on the same location, there exists a potential data race condition. If the race is not handled properly, it could have a wide range of negative consequences. In the best case, there might be data corruption rendering the affected files unreadable and useless; this may not be a major problem if there exist archived, non-corrupted versions of the data. In the worst case, a process (possibly even the operating system itself) may freak out and crash, unable to decide what to do about the unexpected input it receives.


	Traditional data-race detection programs operate by running an isolated runtime and comparing it with the currently active runtime, to find situations that would have resulted in a data race if the runtimes were not isolated. DataCollider operates by temporarily setting up breakpoints at random memory access instances. If a certain memory access hits a breakpoint, DataCollider springs into action. The breakpoint causes the memory access instruction to be postponed, and so the instruction pretty much goes to sleep until DataCollider has finished its job. The job is like taking a before and after photograph of something; DataCollider records the data stored at the address the instruction was attempting to access, then allows the instruction to execute. Then DataCollider records the data again. If the before and after records do not match, then another thread has tampered with the data at the same time that this instruction was trying to read it; this is precisely the definition of a data race.		Traditional data-race detection programs operate by running an isolated runtime and comparing it with the currently active runtime, to find situations that would have resulted in a data race if the runtimes were not isolated. DataCollider operates by temporarily setting up breakpoints at random memory access instances. If a certain memory access hits a breakpoint, DataCollider springs into action. The breakpoint causes the memory access instruction to be postponed, and so the instruction pretty much goes to sleep until DataCollider has finished its job. The job is like taking a before and after photograph of something; DataCollider records the data stored at the address the instruction was attempting to access, then allows the instruction to execute. Then DataCollider records the data again. If the before and after records do not match, then another thread has tampered with the data at the same time that this instruction was trying to read it; this is precisely the definition of a data race.


	Most existing data race detectors use static detection techniques. These involve analysing program source code to determine where simultaneous accesses occur. This method is typically seen as less effective because it produces a warning every time synchronous accesses occur; the program then has to sort out all the false warnings from the legitimate error reports. The problem is that there are no heuristics that can consistently eliminate the false warnings without also eliminating some of the legitimate reports. DataCollider uses a dynamic detection technique, which involves analysing program output and recognizing anomalous data accesses. Dynamic detectors also produce false warnings, but not nearly as often as static detectors.		Most existing data race detectors use static detection techniques. These involve analysing program source code to determine where simultaneous accesses occur. This method is typically seen as less effective because it produces a warning every time synchronous accesses occur; the program then has to sort out all the false warnings from the legitimate error reports. The problem is that there are no heuristics that can consistently eliminate the false warnings without also eliminating some of the legitimate reports. DataCollider uses a dynamic detection technique, which involves analysing program output and recognizing anomalous data accesses. Dynamic detectors also produce false warnings, but not nearly as often as static detectors.

	~~[Don't worry guys; that's not all I've got. I'm still working on it.]~~		--[[User:Abondio2\|Austin Bondio]] 14:47, 2 December 2010 (UTC)

	--[[User:Abondio2\|Austin Bondio]] 01:56, 2 December 2010 (UTC)

	=Research problem=		=Research problem=

Abondio2: /* Background Concepts */

2010-12-02T14:46:09Z

Background Concepts

← Older revision		Revision as of 14:46, 2 December 2010
Line 16:		Line 16:
	Traditional data-race detection programs operate by running an isolated runtime and comparing it with the currently active runtime, to find situations that would have resulted in a data race if the runtimes were not isolated. DataCollider operates by temporarily setting up breakpoints at random memory access instances. If a certain memory access hits a breakpoint, DataCollider springs into action. The breakpoint causes the memory access instruction to be postponed, and so the instruction pretty much goes to sleep until DataCollider has finished its job. The job is like taking a before and after photograph of something; DataCollider records the data stored at the address the instruction was attempting to access, then allows the instruction to execute. Then DataCollider records the data again. If the before and after records do not match, then another thread has tampered with the data at the same time that this instruction was trying to read it; this is precisely the definition of a data race.		Traditional data-race detection programs operate by running an isolated runtime and comparing it with the currently active runtime, to find situations that would have resulted in a data race if the runtimes were not isolated. DataCollider operates by temporarily setting up breakpoints at random memory access instances. If a certain memory access hits a breakpoint, DataCollider springs into action. The breakpoint causes the memory access instruction to be postponed, and so the instruction pretty much goes to sleep until DataCollider has finished its job. The job is like taking a before and after photograph of something; DataCollider records the data stored at the address the instruction was attempting to access, then allows the instruction to execute. Then DataCollider records the data again. If the before and after records do not match, then another thread has tampered with the data at the same time that this instruction was trying to read it; this is precisely the definition of a data race.

	Most existing data race detectors use static detection techniques. These involve analysing program source code to determine where simultaneous accesses occur. This method is typically seen as less effective because it produces a warning every time synchronous accesses occur; the program then has to sort out all the false warnings from the legitimate error reports. The problem is that there are no heuristics that can consistently eliminate the false warnings without also eliminating some of the legitimate reports.		Most existing data race detectors use static detection techniques. These involve analysing program source code to determine where simultaneous accesses occur. This method is typically seen as less effective because it produces a warning every time synchronous accesses occur; the program then has to sort out all the false warnings from the legitimate error reports. The problem is that there are no heuristics that can consistently eliminate the false warnings without also eliminating some of the legitimate reports. DataCollider uses a dynamic detection technique, which involves analysing program output and recognizing anomalous data accesses. Dynamic detectors also produce false warnings, but not nearly as often as static detectors.

	[Don't worry guys; that's not all I've got. I'm still working on it.]		[Don't worry guys; that's not all I've got. I'm still working on it.]

Abondio2: /* Background Concepts */

2010-12-02T14:43:10Z

Background Concepts

← Older revision		Revision as of 14:43, 2 December 2010
Line 15:		Line 15:

	Traditional data-race detection programs operate by running an isolated runtime and comparing it with the currently active runtime, to find situations that would have resulted in a data race if the runtimes were not isolated. DataCollider operates by temporarily setting up breakpoints at random memory access instances. If a certain memory access hits a breakpoint, DataCollider springs into action. The breakpoint causes the memory access instruction to be postponed, and so the instruction pretty much goes to sleep until DataCollider has finished its job. The job is like taking a before and after photograph of something; DataCollider records the data stored at the address the instruction was attempting to access, then allows the instruction to execute. Then DataCollider records the data again. If the before and after records do not match, then another thread has tampered with the data at the same time that this instruction was trying to read it; this is precisely the definition of a data race.		Traditional data-race detection programs operate by running an isolated runtime and comparing it with the currently active runtime, to find situations that would have resulted in a data race if the runtimes were not isolated. DataCollider operates by temporarily setting up breakpoints at random memory access instances. If a certain memory access hits a breakpoint, DataCollider springs into action. The breakpoint causes the memory access instruction to be postponed, and so the instruction pretty much goes to sleep until DataCollider has finished its job. The job is like taking a before and after photograph of something; DataCollider records the data stored at the address the instruction was attempting to access, then allows the instruction to execute. Then DataCollider records the data again. If the before and after records do not match, then another thread has tampered with the data at the same time that this instruction was trying to read it; this is precisely the definition of a data race.

			Most existing data race detectors use static detection techniques. These involve analysing program source code to determine where simultaneous accesses occur. This method is typically seen as less effective because it produces a warning every time synchronous accesses occur; the program then has to sort out all the false warnings from the legitimate error reports. The problem is that there are no heuristics that can consistently eliminate the false warnings without also eliminating some of the legitimate reports.

	[Don't worry guys; that's not all I've got. I'm still working on it.]		[Don't worry guys; that's not all I've got. I'm still working on it.]

Achamney: /* Contribution */

2010-12-02T07:52:46Z

Contribution

← Older revision		Revision as of 07:52, 2 December 2010
Line 36:		Line 36:
	What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)		What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)

	<b>Proving that there is a problem with classic ~~solutions to~~ race detectors:</b><br>		<b>Proving that there is a problem with classic race detectors:</b><br>
	The main contribution that DataCollider provides is the unique idea of using hardware breakpoints in a data race detector. The question is why is a unique idea necessary. Why does DataCollider have to "reinvent the wheel". There has been a plethora of race condition testers invented in the last two decades, and almost all of the dynamic data race detectors can be lumped into three categories. They either implement lock-set, happens-before, or a hybrid of the two types of detection. The research team for DataCollider looked at several of these implementations of race condition testers to find ways of improving their own program, and found that there are major problems in the classic ways of detecting race conditions. <br><br>		The main contribution that DataCollider provides is the unique idea of using hardware breakpoints in a data race detector. The question is why is a unique idea necessary. Why does DataCollider have to "reinvent the wheel". There has been a plethora of race condition testers invented in the last two decades, and almost all of the dynamic data race detectors can be lumped into three categories. They either implement lock-set, happens-before, or a hybrid of the two types of detection. The research team for DataCollider looked at several of these implementations of race condition testers to find ways of improving their own program, and found that there are major problems in the classic ways of detecting race conditions. <br><br>

Line 56:		Line 56:
	<b>PACER: Proportional Detection of Data Races</b>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<br>		<b>PACER: Proportional Detection of Data Races</b>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<br>
	happens-before reasoning<br><br>		happens-before reasoning<br><br>
	Pacer, a happens-before data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two potentially conflicting threads. If the two threads conflict, a data race is thrown, and the state of the program is saved. Pacer samples a percentage of each memory access, (from 1 to 3 percent) and runs the FastTrack ~~happens-before~~ algorithm on each thread that accesses that part of memory. Similar to Pacer, DataCollider samples a percentage of the program's memory accesses, but instead of using vector-clocks to catch the second thread, hardware breakpoints are used. Pacer runs with an overhead of ~~approximatively~~ one to three times the speed of the original program because it ~~takes~~ a ~~considerable~~ amount of processing power to maintain the vector-clocks. Hardware break points are considerably faster than vector-clocks, and as a consequence, DataCollider runs with less overhead than Pacer. <br><br>		Pacer, a happens-before data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two potentially conflicting threads. If the two threads conflict, a data race is thrown, and the state of the program is saved. Pacer samples a percentage of each memory access, (from 1 to 3 percent) and runs the FastTrack algorithm on each thread that accesses that part of memory. Similar to Pacer, DataCollider samples a percentage of the program's memory accesses, but instead of using vector-clocks to catch the second thread, hardware breakpoints are used. Pacer runs with an overhead of approximately one to three times the speed of the original program because it requires a fair amount of processing power to maintain the vector-clocks. Hardware break points are considerably faster than vector-clocks, and as a consequence, DataCollider runs with less overhead than Pacer. <br><br>

	<b>LiteRace: Effective Sampling for Lightweight Data-Race Detection</b>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<br>		<b>LiteRace: Effective Sampling for Lightweight Data-Race Detection</b>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<br>

← Older revision		Revision as of 06:33, 3 December 2010
Line 36:		Line 36:

	<b>Proving that there is a problem with classic race detectors:</b><br>		<b>Proving that there is a problem with classic race detectors:</b><br>
	The main contribution that DataCollider provides is the unique idea of using hardware breakpoints in a data race detector. The question is why is a unique idea necessary. Why does DataCollider have to "reinvent the wheel". There has been a plethora of race condition testers invented in the last two decades, and almost all of the dynamic data race detectors can be lumped into three categories. They either implement lock-set, happens-before, or a hybrid of the two types of detection. The research team for DataCollider looked at several of these implementations of race condition testers to find ways of improving their own program, and found that there are major problems in the classic ways of detecting race conditions. <br><br>		The main contribution that DataCollider provides is the unique idea of using hardware breakpoints in a data race detector. The question is why is a unique idea necessary. Why does DataCollider have to "reinvent the wheel"? There has been a plethora of race condition testers invented in the last two decades, and almost all of the dynamic data race detectors can be lumped into three categories. They either implement lock-set, happens-before, or a hybrid of the two types of detection. The research team for DataCollider looked at several of these implementations of race condition testers to find ways of improving their own program, and found that there are major problems in the classic ways of detecting race conditions. <br><br>

	Some of the programs that were referenced were: <br><br>		Some of the programs that were referenced were: <br><br>
Line 50:		Line 50:
	lock-set based reasoning<br><br>		lock-set based reasoning<br><br>

	Eraser, a data race detector programmed in 1997, was one of the earlier data race detectors invented. It may have been a useful and revolutionary program of its time, however, it uses very low level techniques compared to most data race detectors today. One of the ~~reason~~ why it is unsuccessful is because it only checks whether memory accesses use proper locking techniques. If a memory access is found that does not use a lock, then Eraser will report a data race. In many cases, the misuse of proper locking techniques is a conscious decision by the programmer, so Eraser will report many false positives. Modern locking systems are also very complicated and have several different kinds of locks for different situations. It is difficult for one program to handle upwards of 12 types of locks, especially when they are very complicated. This does not take into account all of the benign problems such as date of access variables. Locking systems are notorious for reporting false positives such as this, and it is near impossible to change the architecture of the algorithm to ignore benign cases. <br><br>		Eraser, a data race detector programmed in 1997, was one of the earlier data race detectors invented. It may have been a useful and revolutionary program of its time; however, it uses very low level techniques compared to most data race detectors today. One of the reason1 why it is unsuccessful is because it only checks whether memory accesses use proper locking techniques. If a memory access is found that does not use a lock, then Eraser will report a data race. In many cases, the misuse of proper locking techniques is a conscious decision by the programmer, so Eraser will report many false positives. Modern locking systems are also very complicated and have several different kinds of locks for different situations. It is difficult for one program to handle upwards of 12 types of locks, especially when they are very complicated. This does not take into account all of the benign problems such as date of access variables. Locking systems are notorious for reporting false positives such as this, and it is near impossible to change the architecture of the algorithm to ignore benign cases. <br><br>


	<b>PACER: Proportional Detection of Data Races</b>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<br>		<b>PACER: Proportional Detection of Data Races</b>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<br>
	happens-before reasoning<br><br>		happens-before reasoning<br><br>
	Pacer, a happens-before data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two potentially conflicting threads. If the two threads conflict, a data race is thrown, and the state of the program is saved. Pacer samples a percentage of each memory access, (from 1 to 3 percent) and runs the FastTrack algorithm on each thread that accesses that part of memory. Similar to Pacer, DataCollider samples a percentage of the program's memory accesses, but instead of using vector-clocks to catch the second thread, hardware breakpoints are used. Pacer runs with an overhead of approximately one to three times the speed of the original program because it requires a fair amount of processing power to maintain the vector-clocks. Hardware break points are considerably faster than vector-clocks, and as a consequence, DataCollider runs with less overhead than Pacer. <br><br>		Pacer, a happens-before data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two potentially conflicting threads. If the two threads conflict, a data race is thrown, and the state of the program is saved. Pacer samples a percentage of each memory access, (from 1 to 3 percent) and runs the FastTrack algorithm on each thread that accesses that part of memory. Similar to Pacer, DataCollider samples a percentage of the program's memory accesses, but instead of using vector-clocks to catch the second thread, hardware breakpoints are used. Pacer runs with an overhead of approximately one to three times the speed of the original program because it requires a fair amount of processing power to maintain the vector-clocks. Hardware break points are considerably faster than vector-clocks, and as a consequence, DataCollider runs with less overhead than Pacer. <br><br>

	<b>LiteRace: Effective Sampling for Lightweight Data-Race Detection</b>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<br>		<b>LiteRace: Effective Sampling for Lightweight Data-Race Detection</b>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<br>
	happens-before reasoning<br><br>		happens-before reasoning<br><br>
	LiteRace, similar to Pacer, samples a percentage of memory accesses from a program. ~~Where it differs is~~ the ~~parts~~ of memory that LiteRace ~~samples the most~~. The "hot spot" regions of memory are ones that are accessed most by the program. Since they ~~are~~ accessed the most, ~~chances are~~ that they have already been successfully debugged, or if there are data races ~~there~~, they are benign. LiteRace detects these areas in memory as hot spots, and samples them at a much lower rate. This improves LiteRace's chances of capturing a valid data race at a much lower sampling rate. ~~Where~~ DataCollider ~~bests~~ LiteRace is based on LiteRace's installing mechanism. LiteRace needs to be recompiled into the software it is trying to debug, whereas ~~DataColleder's~~ breakpoints do not require any code changes to the program. This is a major success for DataCollider because often third party testers do not have the source code for a program. <br><br>		LiteRace, similar to Pacer, samples a percentage of memory accesses from a program. The major difference can be found in the areas of memory that LiteRace selects. The "hot spot" regions of memory are ones that are accessed most by the program. Since they have been accessed the most, the likelihood increases that they have already been successfully debugged, or if there are data races present, they are benign. LiteRace detects these areas in memory as hot spots, and samples them at a much lower rate. This improves LiteRace's chances of capturing a valid data race at a much lower sampling rate. DataCollider proves superior to LiteRace based on LiteRace's installing mechanism. LiteRace needs to be recompiled into the software it is trying to debug, whereas DataCollider’s breakpoints do not require any code changes to the program. This is a major success for DataCollider because often third party testers do not have the source code for a program. <br><br>


Line 65:		Line 65:
	combination of lock-set and happens-before reasoning<br><br>		combination of lock-set and happens-before reasoning<br><br>

	RaceTrack uses a unique technique in order to detect data races. The program being debugged is run on top of RaceTrack as a virtual machine using the .NET framework~~, and it will examine~~ all of the memory accesses that the program requests. As soon as suspicious behavior is exhibited, a warning is sent off to be later evaluated when the program terminates. RaceTrack uses this technique because several process intensive inspections of the state of the machine must be checked~~, and~~ doing this on the fly is expensive. There are many problems with RaceTrack. It is very successful at detecting a vast percentage of data races, however, it has a high overhead and requires extreme amounts of memory. RaceTrack must save the state of the entire machine every time a warning is produced, and it also has to save each threads memory accesses to check which memory access "happened before". Since most warnings thrown are found to be benign, saving the state of the machine wastes computational power and memory. Long running programs also prove to be a problem, where the computer being debugged will run out of memory to store all of the warning states before the program terminates. It then will have to either increase overhead significantly to store the warnings on disk, or it will have to delete some warnings to make room for new ones. <br><br>		RaceTrack uses a unique technique in order to detect data races. The program being debugged is run on top of RaceTrack as a virtual machine using the .NET framework. It examines all of the memory accesses that the program requests. As soon as suspicious behavior is exhibited, a warning is sent off to be later evaluated when the program terminates. RaceTrack uses this technique because several process intensive inspections of the state of the machine must be checked; doing this on the fly is expensive. There are many problems with RaceTrack. It is very successful at detecting a vast percentage of data races; however, it has a high overhead and requires extreme amounts of memory. RaceTrack must save the state of the entire machine every time a warning is produced, and it also has to save each threads memory accesses to check which memory access "happened before". Since most warnings thrown are found to be benign, saving the state of the machine wastes computational power and memory. Long running programs also prove to be a problem, where the computer being debugged will run out of memory to store all of the warning states before the program terminates. It then will have to either increase overhead significantly to store the warnings on disk, or it will have to delete some warnings to make room for new ones. <br><br>

	<b>MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs</b>[http://docs.google.com/viewer?a=v&q=cache:C8gWk-H3GmEJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.73.9551%26rep%3Drep1%26type%3Dpdf+MultiRace:+Efficient+on-the-fly+data+race+detection+in+multithreaded+C%2B%2B+programs&hl=en&gl=ca&pid=bl&srcid=ADGEESj1jYlzXMOwgbh7SVntUsHxVeI1TvmkU8Oslkm-L9gq-NIyglj5eD48rtkcziUQUynmjOmZojsyzw_tBRiLN6T0n6iiDZyUiFjBUfLijQbzNsRpDQCsMpn-xTiIqK2PUj4DXwoM&sig=AHIEtbRBHpMvb5fel3XOi5oASAogumY-rg]<br>		<b>MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs</b>[http://docs.google.com/viewer?a=v&q=cache:C8gWk-H3GmEJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.73.9551%26rep%3Drep1%26type%3Dpdf+MultiRace:+Efficient+on-the-fly+data+race+detection+in+multithreaded+C%2B%2B+programs&hl=en&gl=ca&pid=bl&srcid=ADGEESj1jYlzXMOwgbh7SVntUsHxVeI1TvmkU8Oslkm-L9gq-NIyglj5eD48rtkcziUQUynmjOmZojsyzw_tBRiLN6T0n6iiDZyUiFjBUfLijQbzNsRpDQCsMpn-xTiIqK2PUj4DXwoM&sig=AHIEtbRBHpMvb5fel3XOi5oASAogumY-rg]<br>
	combination of lock-set and happens-before reasoning<br><br>		combination of lock-set and happens-before reasoning<br><br>

	MultiRace is another hybrid style race condition debugger that uses two unique algorithms. The first algorithm, Djit is the ~~happens~~-~~before iteration~~, which ~~INSERT STUFF HERE~~. The second is an improved iteration of the lock-set algorithm. MultiRace is the most similar program to DataCollider in terms of their goals. Both strive to decrease overhead to near standard running times of the program itself, and to increase the program transparency for maximum user compatibility. MultiRace itself is several orders of magnitude more complicated than DataCollider, but since MultiRace hides its complexity from the user with transparency, it is still simple to use. It is arguable that MultiRace is superior for detecting races for C++ programs, however, MultiRace is not compatible with any other programming language. Since DataCollider uses hardware breakpoints, the coding language of the program is irrelevant. Also, since DataCollider avoids using both lock-set and happens before algorithms, it is versatile enough to even debug kernels. <br><br>		MultiRace is another hybrid style race condition debugger that uses two unique algorithms. The first algorithm, Djit+, is the “happens-before” mechanism, which like Pacer uses vector-clocks to track each thread. The second is an improved iteration of the lock-set algorithm. Both of these algorithms are run on sampled sections of memory, and are fully optimized to decrease overhead. MultiRace is the most similar program to DataCollider in terms of their common goals. Both strive to decrease overhead to near standard running times of the program itself, and to increase the program transparency for maximum user compatibility. MultiRace itself is several orders of magnitude more complicated than DataCollider, but since MultiRace hides its complexity from the user with transparency, it is still simple to use. It is arguable that MultiRace is superior for detecting races for C++ programs; however, MultiRace is not compatible with any other programming language. Since DataCollider uses hardware breakpoints, the coding language of the program is irrelevant. Also, since DataCollider avoids using both lock-set and happens before algorithms, it is versatile enough to even debug kernels. <br><br>



	DataCollider is a very unique program. Most other dynamic race condition testers can be lumped into the three groups lock-set, happens-before, or hybrid. DataCollider, however, recognizes the errors of these styles of detection, and manages to avoid them completely. Even though there are issues with false positives and benign races, DataCollider provides very simple, versatile, and lightweight functionality ~~in debugging~~ a ~~program~~. ~~Future programs may take this unique~~ style of race detection ~~and add their own functionality to improve upon it. It could~~ be ~~that DataCollider could inspire~~ a ground breaking solution to race conditions and how to detect them.		DataCollider is a very unique program. Most other dynamic race condition testers can be lumped into the three groups lock-set, happens-before, or hybrid. DataCollider, however, recognizes the errors of these styles of detection, and manages to avoid them completely. Even though there are issues with false positives and benign races, DataCollider provides very simple, versatile, and lightweight functionality. DataCollider opens the door to a whole new category of data race detectors. This style of race detection may be a ground breaking solution to race conditions and how to detect them.

	=Critique=		=Critique=