### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Advanced Topics in Computer Graphics CMPS 290

UCSC

GPA 4.0

### View Full Document

## 31

## 0

## Popular in Course

## Popular in ComputerScienence

This 24 page Class Notes was uploaded by Dr. Elyssa Ratke on Monday September 7, 2015. The Class Notes belongs to CMPS 290 at University of California - Santa Cruz taught by Staff in Fall. Since its upload, it has received 31 views. For similar materials see /class/182267/cmps-290-university-of-california-santa-cruz in ComputerScienence at University of California - Santa Cruz.

## Popular in ComputerScienence

## Reviews for Advanced Topics in Computer Graphics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/07/15

Model Checking 2 Lecture 18 Very hard to predict all possible ways in which thread execution steps can be interleaved Often hard to determinepredict what sequences of actions the environment of a system may generate If you re not convinced let s consider a few very small examples id add0bject o ufferEhead 0 ad headlsize ltaillsize return buffertail Finitestate Program Property 1 m Property 2 m Requirement V M Temporal logi c formula Model Checker Error trace I II Line 5 m Line 12 m Line 15m Line 21m Line 25m Line 27m Line 4lm Line 47m lress requirements Different kinds of temporal logcs Syntax What are the formulas in the logic Semantics What does it mean for model M to satisfy formula p in the logic 739 iii iii p atomic propositions eg X 5 btrue IP p A w p v w satisfaction M satisfies p if all the reachable states satisfy p 1 algorithm Does M satisfy p Start at the initial states and explore the states of M using DFS or BFS At any state if p is violated then print an error tracequot If all reachable states have been visited then say yesquot o rtnching time logic atomic propositions eg X 5 btrue IP p v w EIX p Ekpr 3ch What is satisfy CTL is a state logic Each formula is true or false in a state 5 satisfies atomic propositions if Fs satisfies p p ifs does NOT satisfy p p v w 5 satisfies p or 5 satisfies w 5 satisfies EIX p if there exists t such that Rst and t satisfies p Elq U w if there exists a sequence of states stv such that V satisfies w st a satisfycp EIG p if there exists an infinite sequence of states starting from s where p is always true ii time logic atomic propositions IP p A w p v w p U w imporal Logics Difficult to formalize a requirement in temporal logic Between the window open and the window close button X can be pushed at most twice is rendered in LTL as open ltgtclose gt pushx close U close pushx close U close lpushx close U close pushx close U close pushX U close l7 j i ii gents for programmers Express correctness as assertions in code or in domainspecific language that gets translated into assertions in code Goal Find assertion violations 15 MWM HQ mkudnd Incl l 1 111111 1939 53mm Ell 39 27 quot jam maximum 1 El 36 THEM ng I39Edl iig ijntl W m Ill l ili mm mmmi my mm 1quot J IL us 1 ll mmmw Mlmjnu qmm mw V WWII n 39 puma J mil1m gPHjl39n l J thmmyigm 1m z ELK ES 39 M r 4 liwlii39 n nc kj 39 quot quotah quotquot v quot395 a 3 qu quot quota quot quot quota 1quot quota 39 5 W I II In Whimj j TM WMM EE I1 I m 39 m 39 H I 5 2 m I quot I MLE 7 193quot 5 u 3 M 1 2w 39 WWW Mijt 1 WIanml quot mm ham untrained lid minimal in ll Q mhrmimdi M i 39 a h hg h ff39 3915 Rquot HY mamame THE WERE I9 Walla l M 11 WIW39W in F quoth 51 j I I WFHEL qmchan39ud M 2 threads with n instructions between 2n and 2n1 traces n2 reachable states n threads with 1 instructions n traces 2n reachable states iatate Explosion Partial order reduction Symmetry reduction Garbage collection Fingerprinting Symbolic techniques i Reduction Naive MC approach Explore all interleavings Optimizations What if we know some data is thread local lock protected What if we think some data is thread local lock protected l Reduction Suppose each state is Global data local data of T1 local data of T2 and each thread executes same code Consider states G L L and G L L suppose we ve done DFS from G L L and then we see G L L What do we do How do we generalize this idea Suppose we ve seen state S during DFS and then we later see a different state S that only differs from S in that is has different garbage What do we do How do we do this in general During DFS we ve seen many states 1 2 2 523229 and then we get to a state S How do we efficiently check if we ve seen S before Symbolic Model Checking Diagrams abcd Ordered decision tree for f hash consing fabcd Often compact variable order strongly affects size can blow up Canonical representation for given variable order Efficiently represent a set of states Fast industrialstrength BDD packages A AJA

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.