New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Multicore Cncrt Programming

by: Lisette Hodkiewicz

Multicore Cncrt Programming CS 6030

Lisette Hodkiewicz
GPA 3.83

Ala Al-Fuqaha

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Ala Al-Fuqaha
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 12 page Class Notes was uploaded by Lisette Hodkiewicz on Wednesday September 30, 2015. The Class Notes belongs to CS 6030 at Western Michigan University taught by Ala Al-Fuqaha in Fall. Since its upload, it has received 64 views. For similar materials see /class/216872/cs-6030-western-michigan-university in ComputerScienence at Western Michigan University.

Similar to CS 6030 at WMU

Popular in ComputerScienence


Reviews for Multicore Cncrt Programming


Report this Material


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/30/15
Switch Construction Fall 2007 CS 6030 I Aggregate bandwidth Q 12 ofthe lO bus bandwidth quot WorkstationBased D capacity shared among all hosts connected to sWItch i1 example 1Gbps bus can support 5 x100Mbps ports in theory I Packetsper second r3 must be able to switch small packets i 1300000 packetsper second is achievable 39 Fall 2007 CS 6030 VG bus m mU imam g Il f rf39a e3i lCgt 397 139 Switching Hardware I Design Goals l3 Throughput depends on traf c model liil Scalability a function of n Switch Fabric I Ports 3 Circuit management eg map VCls switch datagrams Ll buffering input andor output I Fabric liil As simple as possible l3 Sometimes do buffering internal Fall 2007 CS 6030 3 Buffering I Wherever contention is possible or Input port contend for fabric l Internal contend for output port 1 Output port contend for link I Headof Line Blocking lulnput buffering Fall 2007 CS 6030 4 Switch Design I Crossbar switches I Banyan Networks I Batcher Networks I Sunshine Switch Fall 2007 CS 6030 Crossbar Switch I Every input port is connected to every output port j NxN I Output ports Complexity scales as ON2 Fall 2007 CS 6030 Crossbar Switch Port Port Output Port Output Port Fall 2007 CS 6030 1 Knockout Switch I Assumption i It is unlikely that N inputs will have packets destined for the same output port Pick L from N packets at a port it Output port maintains L cyclic buffers D Shifter places up to L packets in one cycle 13 Each buffer gets only one packet Lquot Output port uses roundrobin between buffers 1 Arrival order is maintained I Problem 213 Hot spots I Output ports scale as ON Fall 2007 CS 6030 Knockout Switch I Output port design l Packet lters l Recognize packets destined for a speci c port lj Concentrator I Selects up to L packets from those destined for this port I Discards excess packets l Queue I Length L Fall 2007 CS 6030 9 i Knockout Switch Choose L of N 2x2 Ex 20f4 random selector Discard What happens if more than L Del y arrive quotmt Discard Fall 2007 CS 6030 10 7 1 7 SelfRouting Fabrics I Idea ll Use source routing on quotnetworkquot in switch It Input port attaches output port number as header ii Fabric routes packet based on output port I Types Banyan Network Cl Batcher Banyan Network Ci Sunshine Switch Fall 2007 CS 6030 11 Banyan Network I A network of 2x2 switches iEach element routes to output 0 or 1 based on packet header 1A switch at stage i looks at bit i in the header Lo 1 Fall 2007 CS 6030 12 Banyan Network 001 011 110 111 II II II 111 111 110 111 Fall 2007 CS 6030 r i Banyan Network I Perfect Shufer i l N inputs requires log2N stages of N2 switching elements Cl Complexity on order of N log2N I Collisions Cl If two packets arrive at the same switch destined for the same output port a collision will occur Cl lfall packets are sorted in ascending order upon arrival to a banyan network no collisions will occur Fall 2007 CS 6030 7 1 Batcher Network I Performs merge sort I A network of 2x2 switches 1 Each element routes to output 0 or 1 based on packet header 2 A switch at stage i looks at the whole header 1 Two types of switches Up switch a Sends higher number to top output 0 Down switch a Sends higher number to bottom output 1 Fall 2007 CS 6030 15 Batcher Network Fall 2007 CS 6030 16 Batcher Network Fall 2007 CS 6030 17 Batcher Network I How it really works iii Merger is presented with a pair of sorted lists one in ascending order one in descending order El First stage of merger sends packets to the correct half of the network E Second stage sends them to the correct quarter I Size 1 N2 switches per stage iii log2N x 1 log2N2 stages iii Complexity N log22N Fall 2007 CS 6030 18 Batcher Banyan Network I Idea quot3 Attach a batcher network backtoback with a banyan network 3 Arbitrary unique permutations can be routed without contention i j Two packets destined for same output port still collide Fall 2007 CS 6030 Batcher Banyan Switch Architecture Simple components with no buffering filter eliminates duplicates by comparing consecutive addresses and returns ack to inputs 0 adder computes and inserts rank of cells 39 concentrator uses rank as output address routing network delivers to output 393 I Adder concentrator and routing network all have logzn stages conc is reverse banyan routing net is banyan Fall 2007 CS 6030 Sunshine Switch I Sunshine Switch r3 Like a knockout switch Can handle up to L packets per output port I Recirculates overflow packets If more than L packets arrive for any output port in one cycle Elements I3 Multiple Banyan networks Enables multiple packets per output port Delay Box Excess K packets are recirculated and resubmitted to the switch El Batcher network N new packets K delayed packets Ci i3 Tra I Identifies packets destined for banyan Identifies excess pac ets fl Selector Routes multiple packets for same output on separate banyans Fall 2007 CS 6030 Sunshine Switch Fall 2007 CS 6030 References I Robin Kravets Switching Hardware UIUC CSECE 438 Fall 2007 CS 6030 23


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

Jim McGreen Ohio University

"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.