Parallel ProcessingTypes of Parallel ProcessingStages of Parallel ComputationArtificial IntelligenceArtificial Intelligence ChallengesTerminologyMore TerminologyOraclesThe Hierarchy of ProblemsNP-Complete ProblemsGiven a Problem, How do you Determine if it is Computable?Parallel Processing•Parallel Processing occurs when more than one processor works together to solve a single problem.•Your lab has a lot of PC's but that doesnt mean parallel processing is going on. Each separate PC is working on solving separate problems. •Parallel processing speeds up solution times in two ways:–Multiple computers simply add "horsepower" to an existing algorithm–New algorithms can be designed to actually lower the cost of the problem solution.•Two kinds of parallelism:–Data parallelism: when the data is divided up among processors–Task parallelism: When the parts of an algorithm are divided up.Types of Parallel Processing•Pipelining (not usually considered true parallelism)–This occurs when separate processers, each with a specific job, work on a phase of a problems solution.–Most common example is your PC. The "single" processor is actually made up of many smaller special purpose processors.•Parallel Processing–Separate processors, usually identical work with one memory.–Usually requires special purpose machines. These machines may contain thousands of simple processors (usually in a multiple of 2, like 4096 or 8192, etc)•Distributed Processing–Separate processors of any type each with their own memory.–Networks or the internet. This is the most general and flexible type of processing, but communication costs between processors may be high.Stages of Parallel Computation•Everything has a benefit and a cost - parallel processing has an overhead cost. •The goal is to let the benefit of multiple processors working on a single problem outweigh the cost of keeping track of them. •Stages of a parallel computation:–(cost) Division of problem/data and distribution to processors–(cost) Start up of remote processes–(benefit) Parallel Computation–(cost) Transfer local results to a common processor–(cost) Collate results and presentArtificial Intelligence•Artificial Intelligence (AI) is the name given to encoding intelligent or humanistic behaviors in computer software.•Problem: Nobody has created a widely accepted definition of intelligence.–At one time was considered a uniquely human quality.–Now generally accepted to be an animal quality.–Has been linked to tool use, tool creation, learning, adaptation to novel situations, capacity for abstraction.•Problem: Nobody has created a widely accepted definition of artificial intelligence.–Cognitive models attempt to recreate the actual processes of the human brain.–Behavioral models attempt to produce behavior that is reasonable for a situation regardless of how the behavior was produced.–Tend to focus on reasoning, behavior, learning, adaptation.Artificial Intelligence Challenges•Ambiguity – Knowledge ultimately represents natural phenomena that are inherently ambiguous. How do we resolve this?•Size of Knowledge – How do you store it all? Once stored how do you access only the pertinent items and skip over irrelevant items.–Humans are good at this, though we don’t know why. •Relationships between Pieces of Knowledge – This is worse than the size of knowledge. –Given n items and m types of relationships, there are m*(n2) possible relationships.–Is it better to explicitly represent relationships or derive them in real time as we need them?Terminology•Closed Problems: These problems are well understood. The known cost and known algorithms are of the same order. It is known whether they are computable or not•Open Problems: These problems are not as well understood. The cost of known algorithms to solve them and the theoretical best are not of the same order. •Tractable: Computable, specifically with respect to cost. Cost is polynomial.•Intractable: Not computable, specifically with respect to cost. Cost is exponential or worse.More Terminology•Undecidable Problems: These are problems for which no algorithm can be written (regardless of cost). They are not computable.•Deterministic Algorithms: Algorithms that have no randomness associated with them. They will always behave the same when given the same input.•Nondeterministic Algorithms: Algorithms that have random elements. They may behave differently when run repeatedly,even if the input is the same.Oracles•Oracles: A theoretical device that magically selects the correct choice for an algorithm when the algorithm has choices to make. •They don't exist, but are used to classify the "hardness" of problems. •Example: Traveling Salesman with oracle–We want to travel to n cities.–Recall that Traveling Salesman is an O(n!) problem.–With an oracle, we always make the best choice on each leg of the trip.–This means we only check out one path, and it is the optimal path. –Since there are n cities, we made n correct choices and the problem is O(n).•Since Traveling Salesman is intractable without the oracle, but tractable with the oracle, Traveling Salesman is an NP problem.The Hierarchy of ProblemsPNPHardP = Polynomial, O(nk).Easy to solve, easy to verify solution.Ex: Searching, sorting.NP = Non-Deterministic Polynomial, O(kn)Hard to solve, easy to verify solutionEx: Traveling Salesman Decision.Hard = Hard, O(kn)Hard to solve, hard to verify solution.Ex: Listing all n-digit numbers.NP-Complete Problems•There are literally hundreds of them.•They can all be mapped to each other (hence the "complete" part of the name).•They all have exponential upper bound costs (not computable).•They all have polynomial lower bound costs (computable). •It is possible that polynomial algorithms will be developed to solve one of them–If one is solved quickly, then they all are.–Until then the notion of nondterministic algorithm guided by an oracle is used to discuss them.Given a Problem, How do you Determine if it is Computable?•Method One (usually the hard way):–Write an algorithm to compute the solution for all inputs.–Determine the cost of the algorithm.–Compare to the problem hierarchy.•Method Two (usually the easy way):–Show that the new problem can be mapped to a known problem.–The new problem then has the same cost as the old.–If the old was computable, then so is