X

Download Chess Game PowerPoint Presentation

SlidesFinder-Advertising-Design.jpg

Login   OR  Register
X


Iframe embed code :



Presentation url :

Home / Sports & Recreation / Sports & Recreation Presentations / Chess Game PowerPoint Presentation

Chess Game PowerPoint Presentation

Ppt Presentation Embed Code   Zoom Ppt Presentation

PowerPoint is the world's most popular presentation software which can let you create professional Chess Game powerpoint presentation easily and in no time. This helps you give your presentation on Chess Game in a conference, a school lecture, a business proposal, in a webinar and business and professional representations.

The uploader spent his/her valuable time to create this Chess Game powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by onlinesearch in Sports & Recreation ppt presentation category is available for free download,and can be used according to your industries like finance, marketing, education, health and many more.

About This Presentation

Slide 1 - Iterative Context Bounding for Systematic Testing of Multithreaded Programs Madan Musuvathi Shaz Qadeer Microsoft Research
Slide 2 - Testing multithreaded programs is HARD Specific thread interleavings expose subtle errors Testing often misses these errors Even when found, errors are hard to debug No repeatable trace Source of the bug is far away from where it manifests
Slide 3 - Current practice Concurrency testing == Stress testing Example: testing a concurrent queue Create 100 threads performing queue operations Run for days/weeks Pepper the code with sleep( random() ) Stress increases the likelihood of rare interleavings Makes any error found hard to debug
Slide 4 - CHESS: Unit testing for concurrency Example: testing a concurrent queue Create 1 reader thread and 1 writer thread Exhaustively try all thread interleavings Run the test repeatedly on a specialized scheduler Explore a different thread interleaving each time Use model checking techniques to avoid redundancy Check for assertions and deadlocks in every run The error-trace is repeatable
Slide 5 - State space explosion x = 1; y = 1; x = 2; y = 2; 2,1 1,0 0,0 1,1 2,2 2,2 2,1 2,0 2,1 2,2 Thread 1 Thread 2 1,2 2,0 2,2 1,1 1,1 1,2 1,0 1,2 1,1 y = 1; x = 1; y = 2; x = 2; Init state: x = 0, y = 0
Slide 6 - x = 2; … … … … … y = 2; State space explosion Thread 1 Thread n x = 1; … … … … … y = 1; … n threads k steps each Number of executions = O( nnk ) Exponential in both n and k Typically: n < 10 k > 100 Limits scalability to large programs (large k)
Slide 7 - Techniques Iterative context bounding Strategy for searching large state spaces State space optimization Reduces the size of the state space
Slide 8 - x = 1; if (p != 0) { x = p->f; } Iterative context bounding Prioritize executions with small number of preemptions Two kinds of context switches: Preemptions – forced by the scheduler e.g. Time-slice expiration Non-preemptions – a thread voluntarily yields e.g. Blocking on an unavailable lock, thread end x = p->f; } x = 1; if (p != 0) { p = 0; Thread 1 Thread 2 preemption non-preemption
Slide 9 - Iterative context-bounding algorithm The scheduler has a budget of c preemptions Nondeterministically choose the preemption points Resort to non-preemptive scheduling after c preemptions Run each thread to the next yield point Once all executions explored with c preemptions Try with c+1 preemptions Iterative context-bounding has desirable properties Property 0: Easy to implement
Slide 10 - Property 1: Polynomial state space n threads, k steps each, c preemptions Number of executions <= nkCc . (n+c)! = O( (n2k)c. n! ) Exponential in n and c, but not in k x = 1; … … … … … y = 1; x = 2; … … … … … y = 2; Thread 1 Thread 2 x = 1; … … … … x = 2; … … … … y = 1; … … y = 2; Choose c preemption points Permute n+c atomic blocks
Slide 11 - Property 2: Deep exploration possible with small bounds A context-bounded execution has unbounded depth A thread may execute unbounded number of steps within each context Can reach a terminating state from an arbitrary state with zero preemptions Perform non-preemptive scheduling Leave the number of non-preemptions unbounded
Slide 12 - Property 3: Coverage metric If search terminates with c preemptions, any remaining error must require at least c+1 preemptions Intuitive estimate for the complexity of the bugs remaining in the program the chance of their occurrence in practice
Slide 13 - Property 4: Finds the ‘simplest’ error trace Finds the smallest number of preemptions to the error Number of preemptions better metric of error complexity than execution length
Slide 14 - Property 5: Lots of bugs with small number of preemptions
Slide 15 - Most states are covered with small number of preemptions
Slide 16 - Coverage vs Time (Dryad)
Slide 17 - Techniques Iterative context-bounding Strategy for searching large state spaces State space optimization
Slide 18 - Optimization for race-free programs Insert context-switches only at synchronization points Massive state-space reduction Num steps (k) = num synch. operations (not memory accesses) Run data-race detection to check race-free assumption Goldilocks algorithm [PLDI ’07] implemented for x86 Theorem: When search terminates for context-bound c Either find an erroneous execution Or find a data-race Or the program has no errors reachable with c preemptions
Slide 19 - Conclusion Iterative context-bounding algorithm Effective search strategy for multi-threaded bugs Exposes many concurrency bugs Implemented in the CHESS model checking tool Applying CHESS to Windows drivers, SQL, Cosmos, Singularity Visit http://research.microsoft.com/projects/CHESS/
Slide 20 - Extra Slides
Slide 21 - Partial-order reduction Many thread interleavings are equivalent Accesses to separate memory locations by different threads can be reordered Avoid exploring equivalent thread interleavings T1: x := 1 T2: y := 2 T2: y := 2 T1: x := 1
Slide 22 - Optimistic dynamic partial-order reduction Algorithm [Bruening ‘99] : Assume the program is data-race free Context switch only at synchronization points Check for data-races in each execution Theorem [Stoller ‘00] : If the algorithm terminates without reporting races Then the program has no assertion failures Massive reduction: k = number of synchronization accesses (not memory accesses)
Slide 23 - Combining with context-bounding Algorithm: Assume the program is data-race free Context switch only at synchronization points Explore executions with c preemptions Check for data-races in each execution Theorem: If the algorithm terminates without reporting races, Then the program has no assertion failures reachable with c preemptions Requires that a thread can block only at synchronization points
 

Frequently Asked Questions

> About SlidesFinder?

Slidesfinder is a website that allows users to upload and share their PowerPoint presentations online. It provides a platform for individuals and businesses to share their ideas and knowledge through presentations, and for others to view and download these presentations for educational or professional purposes.
Slidesfinder offers a wide range of presentation topics and categories, including business, education, science, technology, health, and more. Users can also search for presentations using keywords, tags, or by category. The website provides tools to create professional presentations with rich media, animations, and graphics.



One of the key features of Slidesfinder is its user-friendly interface, which allows users to easily upload, view, and share presentations. Users can also embed their presentations in their websites or blogs using the website's embed code feature.
Slidesfinder also offers premium services, such as the ability to create private presentations and to download presentations in high-quality formats. However, the basic features of Slidesfinder are free to use, making it accessible to anyone who wants to share their ideas and knowledge through presentations.

> How do I register with SlidesFinder?

Go to registration page (you can see signup link on top of website page) https://www.slidesfinder.com/signup . If you have facebook/gmail account them just click on SIGN IN WITH FACEBOOK OR SIGN IN WITH GOOGLE button, by this you will be a registered member of slidesfinder without filling any form, required detail automatically will be fatch from your account. If you do not a Facebook account, then click on "Signup". Fill all required fields and you will be a registered member of slidesfinder.

> Is slidesfinder account confirmation is mandatory?

Yes it is mandetory to active your account to login.

> Do I need to signup/login on SlidesFinder before uploading a PowerPoint presentation?

Yes, you need to login with your account before uploading presentation. Your username will be displayed on your uploaded presentation. Your registered email id is needed for sending your stats of uploaded presentation.

Slidesfinder is a sharing website for PowerPoint presentations search and share. Find your interest in the form of powerpoint presentations on slidesfinder and save your valuable time . On Slidesfinder you get presentations from our huge library of professional ppt presentations. We believe in making your search INFORMATIVE and FUN. Find your best ppt presentation from a pool of PowerPoint presentations stacked under important industry categories like business & management, heath & Wellness,eduction & training etc. We provide unique informative PowerPoint presentation for marketers, presenters and educationists. These professional PowerPoint presentations are uploaded by professionals from across numerous industry segments.These ppt presentations are available for FREE download.

Not just finding your interest, but facilitate you broadcast your interest. We have created this platform for easy sharing of PowerPoint presentations, ensuring that these presentations get maximum exposure. Create your slidesfinder account and upload PowerPoint presentations for free, share on social media platforms and BUILD YOUR CROWD WITH PRESENTATION !!

The Great Buddha says, "Share your knowledge.It’s a way to achieve immortality"! So, start sharing knowledge and we are here to make that immortal !!

© 2013-2024 SlidesFinder. All rights reserved.

Re-productivity of content are not allowed. Without prior written permission from author, commercial use of any content is illegal.