Talk:COMP 3000 Essay 2 2010 Question 6 - Revision history

Nshires: /* Critique */

2010-12-02T19:11:47Z

Critique

← Older revision		Revision as of 19:11, 2 December 2010
Line 115:		Line 115:

	I added a few things to the what you wrote and I also moved it to the main page. --[[User:Azemanci\|Azemanci]] 03:22, 2 December 2010 (UTC)		I added a few things to the what you wrote and I also moved it to the main page. --[[User:Azemanci\|Azemanci]] 03:22, 2 December 2010 (UTC)

	Nice :P maybe something on how they tested their program, and if thier testing was sufficient? [[User:Nshires\|Nshires]] 19:11, 2 December 2010 (UTC)		Nice :P maybe something on how they tested their program, and if thier testing was sufficient? [[User:Nshires\|Nshires]] 19:11, 2 December 2010 (UTC)

Nshires: /* Critique */

2010-12-02T19:11:34Z

Critique

← Older revision		Revision as of 19:11, 2 December 2010
Line 115:		Line 115:

	I added a few things to the what you wrote and I also moved it to the main page. --[[User:Azemanci\|Azemanci]] 03:22, 2 December 2010 (UTC)		I added a few things to the what you wrote and I also moved it to the main page. --[[User:Azemanci\|Azemanci]] 03:22, 2 December 2010 (UTC)
			Nice :P maybe something on how they tested their program, and if thier testing was sufficient? [[User:Nshires\|Nshires]] 19:11, 2 December 2010 (UTC)

Abujaki at 13:32, 2 December 2010

2010-12-02T13:32:27Z

← Older revision		Revision as of 13:32, 2 December 2010
Line 12:		Line 12:
	- David Krutsko :: dkrutsko at connect.carleton.ca		- David Krutsko :: dkrutsko at connect.carleton.ca

	If everyone could just post ~~there~~ names and contact information.--[[User:Azemanci\|Azemanci]] 02:57, 15 November 2010 (UTC)		- Andrew Bujaki ==> abujaki [at] connect.carleton.ca

			If everyone could just post their names and contact information.--[[User:Azemanci\|Azemanci]] 02:57, 15 November 2010 (UTC)

	<b>IMPORTANT</b><br>		<b>IMPORTANT</b><br>

Achamney: /* Contribution */

2010-12-02T06:05:09Z

Contribution

← Older revision		Revision as of 06:05, 2 December 2010
Line 89:		Line 89:
	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, 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>

	<b>MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs</b><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>

Achamney: /* Contribution */

2010-12-02T06:02:52Z

Contribution

Achamney: /* Contribution */

2010-12-02T05:59:34Z

Contribution

← Older revision		Revision as of 05:59, 2 December 2010
Line 57:		Line 57:
	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?)

	~~Ill do Contribution: [[User:Achamney\|Achamney]] 03:50, 22 November 2010 (UTC)<br><br><br>~~		<b>Proving that there is a problem in classic solutions to 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 all of the dynamic data race detectors can be lumped into three categories. They can either be 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 to see that there are major problems in the classic ways of detecting race conditions. <br>
	<b>Proving that ~~DataCollider~~ is ~~better~~:</b><br>
	The ~~key part~~ of the ~~contribution~~ of ~~this essay is its competition~~. The research team for DataCollider looked at several ~~other~~ implementations of race condition testers to find ways of improving their own program, or to ~~look for different~~ ways of ~~solving the same problem~~. <br>

	Some of the programs that were referenced were: <br><br>		Some of the programs that were referenced were: <br><br>
Line 68:		Line 66:
	* PACER: Proportional Detection of Data Races<br>		* PACER: Proportional Detection of Data Races<br>
	* LiteRace: Effective Sampling for Lightweight Data-Race Detection<br>		* LiteRace: Effective Sampling for Lightweight Data-Race Detection<br>
	* FastTrack: Efficient and Precise Dynamic Race Detection<br>
	* MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs<br>		* MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs<br>
	* RacerX: Effective, Static Detection of Race Conditions and Deadlocks<br><br><br>

	<b>Eraser: A Dynamic Data Race Detector for Multithreaded Programs</b><br>		<b>Eraser: A Dynamic Data Race Detector for Multithreaded Programs</b><br>

Achamney: /* Contribution */

2010-12-02T05:40:07Z

Contribution

← Older revision		Revision as of 05:40, 2 December 2010
Line 90:		Line 90:
	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.		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>

	<b>~~HIGH OVERHEAD~~</B>~~[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]~~

	<b>MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs</b><br>		<b>MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs</b><br>
	~~combo~~ 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.





			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>



	~~I've noticed~~ a ~~couple things for controversy~~, ~~even though its not my topic~~		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.
	~~The biggest thing i saw was that dataCollider reports non~~-~~erroneous operations 90% of the time~~. ~~This makes~~ the ~~user have to sift through all~~ of ~~the reports~~ to ~~separate the problems from the~~ benign races. ~~[[User:Achamney\|Achamney]] 17:18, 22 November 2010 (UTC)<br>~~

	=Background Concepts=		=Background Concepts=

Achamney: /* Contribution */

2010-12-02T05:09:56Z

Contribution

← Older revision		Revision as of 05:09, 2 December 2010
Line 97:		Line 97:
	combo of lock-set and happens-before reasoning<br><br>		combo 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.

Achamney: /* Contribution */

2010-12-02T04:06:44Z

Contribution

← Older revision		Revision as of 04:06, 2 December 2010
Line 78:		Line 78:


	<b>PACER: Proportional Detection of Data Races</b><br>		[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]<b>PACER: Proportional Detection of Data Races</b><br>
	happens-before reasoning<br><br>		happens-before reasoning<br><br>
	Pacer, a happens-before reasoning data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two threads, and find whether or not they are conflicting in any way. Pacer samples some 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. DataCollider used this source as an example of the implementation of sampling. Similar to Pacer, DataCollider samples some memory accesses, but instead of using vector-clocks to catch the second thread, they use hardware break points. Hardware break points are considerably faster, and cause DataCollider to run much faster than Pacer. <br><br>		Pacer, a happens-before reasoning data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two threads, and find whether or not they are conflicting in any way. Pacer samples some 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. DataCollider used this source as an example of the implementation of sampling. Similar to Pacer, DataCollider samples some memory accesses, but instead of using vector-clocks to catch the second thread, they use hardware break points. Hardware break points are considerably faster, and cause DataCollider to run much faster than Pacer. <br><br>
Line 88:		Line 88:

	<b>RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Trackings</b><br>		<b>RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Trackings</b><br>
	~~combo~~ 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.

	<b>HIGH OVERHEAD</B>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]		<b>HIGH OVERHEAD</B>[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]

Azemanci at 03:56, 2 December 2010

2010-12-02T03:56:50Z

← Older revision		Revision as of 03:56, 2 December 2010
Line 1:		Line 1:
			Alright so its due tomorrow. I was hoping to get an idea of when everyone will be posting there completed sections thanks. --[[User:Azemanci\|Azemanci]] 03:56, 2 December 2010 (UTC)


	'''Actual group members'''		'''Actual group members'''

← Older revision		Revision as of 06:02, 2 December 2010
Line 58:		Line 58:

	<b>Proving that there is a problem in classic solutions to race detectors:</b><br>		<b>Proving that there is a problem in classic solutions to 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 all of the dynamic data race detectors can be lumped into three categories. They can either be 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 to see that there are major problems in the classic ways of detecting race conditions. <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 all of the dynamic data race detectors can be lumped into three categories. They can either be 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 to see 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 66:		Line 66:
	* PACER: Proportional Detection of Data Races<br>		* PACER: Proportional Detection of Data Races<br>
	* LiteRace: Effective Sampling for Lightweight Data-Race Detection<br>		* LiteRace: Effective Sampling for Lightweight Data-Race Detection<br>
	* MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs<br>		* MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs<br><br>

	<b>Eraser: A Dynamic Data Race Detector for Multithreaded Programs</b><br>		<b>Eraser: A Dynamic Data Race Detector for Multithreaded Programs</b>[http://delivery.acm.org/10.1145/270000/265927/p391-savage.pdf?key1=265927&key2=7323721921&coll=DL&dl=ACM&CFID=116768888&CFTOKEN=55577437]
			<br>
	lock-set based reasoning<br><br>		lock-set based reasoning<br><br>

Line 74:		Line 75:


	[http://www.cs.ucla.edu/~dlmarino/pubs/pldi09.pdf]~~<b>PACER: Proportional Detection of Data Races</b>~~<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 reasoning data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two threads, and find whether or not they are conflicting in any way. Pacer samples some 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. DataCollider used this source as an example of the implementation of sampling. Similar to Pacer, DataCollider samples some memory accesses, but instead of using vector-clocks to catch the second thread, they use hardware break points. Hardware break points are considerably faster, and cause DataCollider to run much faster than Pacer. <br><br>		Pacer, a happens-before reasoning data race detector, uses the FastTrack algorithm to detect data races. FastTrack uses vector-clocks to keep track of two threads, and find whether or not they are conflicting in any way. Pacer samples some 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. DataCollider used this source as an example of the implementation of sampling. Similar to Pacer, DataCollider samples some memory accesses, but instead of using vector-clocks to catch the second thread, they use hardware break points. Hardware break points are considerably faster, and cause DataCollider to run much faster than Pacer. <br><br>

	<b>LiteRace: Effective Sampling for Lightweight Data-Race Detection</b><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. 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>


	<b>RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Trackings</b><br>		<b>RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Trackings</b>[http://delivery.acm.org/10.1145/1100000/1095832/p221-yu.pdf?key1=1095832&key2=8433721921&coll=DL&dl=ACM&CFID=116768888&CFTOKEN=55577437]<br>
	combination of lock-set and happens-before reasoning<br><br>		combination of lock-set and happens-before reasoning<br><br>