COMPUTER SCIENCE CURRICULUM
Download
Report
Transcript COMPUTER SCIENCE CURRICULUM
COMPUTER SCIENCE:
STUDY AND RESEARCH
Lan Jin Tsinghua University
California State University-Fresno
KNOWLEDGE AREAS OF CS CURRICULUM
COMPUTER SCIENCE CURRICULUM
AT CSU-FRESNO
STUDENTS’ LEARNING
DESIGNING A COMPUTER ON A BILLIONTRANSISTOR CHIP
DISTRIBUTED SYSTEMS SERVE THE ALWAYSON WORLD
DISTRIBUTED SOFTWARE DEVELOPMENT
Knowledge Areas of CS Curriculum
Discrete Structures
Programming Fundamentals
Algorithms and Complexity
Programming Languages
Architecture and Organization
Operating Systems
Net-centric Computing
Knowledge Areas of CS Curriculum
(continued)
Human-Computer Interaction
Graphics and Visual Computing
Intelligent Systems
Information Management
Software Engineering
Social and Professional Issues
Computational Science
Web site: http://computer.org/education/curricula2001.htm
CS CURRICULUM AT CSU-FRESNO
Core Courses (28+15 units)
Math75,76: College Calculus
CSci1: Critical Thinking & C. S.
CSci40: Intro. to Prog. & Problem
Solving
CSci41: Intro. to Data Structures
CSci60: Foundations of C. S.
CSci112: Intro. To Computer Systems
CSci113: Intro. To Comp. Organization
CSci115: Algorithms & Data Structures
CSci117: Structures of Prog. Languages
CSci119: Intro. To Finite Automata
CSci144: Intro. To Operating Systems
40
1
Math75
41
112
Math76
60
115
119
113
172
154
117
144
124
126
134
136
164
166
146
156
174
148
186
176
177
150
188 152 173
CS CURRICULUM AT CSU-FRESNO
5 electives (15-17 units)
CSci124: Intro. of File Processing
CSci134: Compiler Design
CSci150: Intr. of Software Engg.
CSci154: Simulation
CSci156: Internetworking
Systems & Protocols
191T
CSci164: A.I. Programming
CSci172: Computer Graphics
CSci174: Design & Anal. Of Algorithms
CSci176: Parallel Processing
CSci186: Formal Lang. & Automata
CSci191T: Proseminar (Topic course)
40
1
190
Math75
41
112
Math76
60
194
198
115
119
113
172
154
117
144
124
126
134
136
164
166
146
156
174
148
186
176
177
150
188 152 173
CS CURRICULUM AT CSU-FRESNO
3 of Sequences (9-12 units)
CSci124,126: Data Base Systems
CSci134,136: Compiler Construction
CSci164,166: Artificial Intelligence
CSci150,152: Software Engineering
CSci176,177: Computer Architecture
(Parallel/Distributed Processing)
115
124
126
112
115
119
134
136
117
164
166
CSci172,173: Computer Graphics
CSci186,188: Theory of Computation
CSci144,146: System Architecture
CSci144,148: System Programming
CSci170 (191T): Web Programming
144
144
115
146
148
170
113
144
176
177
119
186
188
Mat h76
41
112
41
150
152
172
173
CS CURRICULUM AT CSU-FRESNO
Graduate Courses (x+30 units)
CSci200: Intro. to Research in C.S.
CSci174: Design & Anal of Algorithms
or CSci188: Intro. To Computability
CSci213: Computer Organization
CSci217: Prog. Language Principles
CSci298: Research Project or
CSci299: Master’s Thesis
40
115
119
124
200
226
144
174
274
Mat h76
112
117
126
CSci226: DB; CSci244: OS
CSci250: SE; CSci264: AI
CSci272: CG; CSci282: TC
CSci246: PP; CSci252: SDE
CSci274: Combinatorial Algo.
CSci284: Automata Theory
Mat h75
41
60
188
282
186
284 244
113
150
164
246
217
264
172
213 250 252 272 298 299 290 291T
STUDENTS’ LEARNING
A set of GE courses required for all majors.
Flexible plan of study for each individual
student, restricted only by prerequisites.
Minimum GPA for graduation; probation
otherwise.
Rigid course requirement & highly competitive job market push the study.
Co-OP program offers opportunity of full-time
employment before graduation for 1 sem.
TAs, GAs, and Awards at different levels.
DESIGNING A COMPUTER ON A
BILLION-TRANSISTOR CHIP
IC technology obeys Moore’s Law
◊ Computing power becomes half as expensive every
18-24 months.
◊ No. of transistors per chip doubles every ≈ 18 months.
Predicted IC by 2005 Roadmap of SIA
◊ 200 M transistors, 0.1µm feature size
◊ 2.0-3.5 GHz
◊ 0.9-1.2 V, dynamic power could be 150W!
DESIGNING A COMPUTER ON A
BILLION-TRANSISTOR CHIP
(Basic Approaches)
Straightforward approach - to add more of:
◊ on-chip multilevel cache and prefetch buffers
◊ hardware contexts and registers
◊ large distributed on-chip DRAM
◊ processors or processing elements
Extending traditional architectures
◊ a higher degree of ILP
◊ new possibility of prediction and speculation
◊ the ability of overcoming memory latencies
◊ on-chip multiprocessing and multithreading
Cooperating distributed system on a chip
Co-designed virtual machine
DESIGNING A COMPUTER ON A
BILLION-TRANSISTOR CHIP
(extending ILP architecture)
Deeper pipeline
IF
ID
IF
instructions
sp ee d u p
EX M WB
ID EX M
IF ID EX
IF ID
IF
time
WB
M WB
EX M WB
ID EX M WB
p ip e lin e d e p th
1 + p ip elin e s ta ll cy cle s / in s tru ctio n
Increasing use of prediction and speculation
Advanced superscalar processing
Wider instruction window
Highly intelligent optimizing compiler
DESIGNING A COMPUTER ON A
BILLION-TRANSISTOR CHIP
(Proposed New Processor Architectures)
Advanced Superscalar: 16 or
Superspeculative Processor:
32 instr/cycle
◊ aggressive fine-grained speculation at every step
Simultaneous Multithread Processor
Trace (multiscalar) Processor
(SMT)
◊ coarse-grained traces on distr. multiple cores
Vector
Intelligent RAM proc. (V-IRAM)
◊ couple vector exec. with large, high-bw DRAM
On-chip Multiprocessor (CMP)
◊ the ability of overcoming memory latencies
RAW (configurable) Processor
◊ Compiler customizes the h/w to each application
DISTRIBUTED SYSTEMS SERVE THE
ALWAYS-ON WORLD(DS FUNDAMENTALS)
Internet — the world-wide distributed system.
DS = Multiple computers + communication network
+ message passing + single system image
Lack of central memory and a global clock
Transparency with no knowledge of what, where, and
how the processors execute the job.
Challenges of Distributed System:
◊ Transparency: access, location, mobility, replication,
concurrency, parallelism, scaling, failure, network
◊ Heterogeneity: network, computer h/w, OS, prog.
languages, vendors
◊ Openness, Scalability , Reliability, Availability, Security, …
DISTRIBUTED SYSTEMS SERVE THE
ALWAYS-ON WORLD(CLIENT-SERVER MODEL)
Server can in turn
be a client
Partitioned or
replicated servers
Proxy servers
and caches
Mobile code
Mobile agent
Network computer
Thin client
Server
request
Client
Client
reply
Server
request
reply
Client
proxy
server
Client
Client
Applet code
Client
Applet
code
(Local site)
Server
Web
Server
Web
Server
Web
Server
Web
Server
DISTRIBUTED SYSTEMS SERVE THE
ALWAYS-ON WORLD(Types of Networks)
Personal Area Network (PAN), WPAN (wireless)
Bluetooth: 10m range, 1 Mbps,
Local Area Network (LAN), WLAN (wireless)
WaveLAN (IEEE802.11b): 1-11 Mbps over 150m
Metropolitan Area Network (MAN)
ATM: 155-622 Mbps over 2-50 Km, latency < 1 ms
Wide Area Network (WAN)
0.010-600 Mbps, latency 100-500 ms (additional
250 ms for satellite transmission)
Internetworks, the Internet
DISTRIBUTED SYSTEMS SERVE THE
ALWAYS-ON WORLD(Internet Protocols)
TCP directly supports applications (e.g., HTTP)
TCP — reliable connection-oriented communication
UDP — unreliable connectionless communication
IP datagrams — basic Internet transmission mechanism
supporting WAN application
Internet application protocols: HTTP, SMTP, FTP, telnet,
NNTP by TCP; DNS by UDP
Layers
Message
Internetworking
Application
Messages (UDP) or streams (TCP)
Transport
UDP or TCP packets
Internetwork
Internetwork packets
IP datagrams
Network-specific packets
Network-specific frames
Network interface
Underlying network
Internet
DISTRIBUTED SYSTEMS SERVE THE
ALWAYS-ON WORLD(Wireless Internet)
WAP (Wireless Application Protocol)
Wireless network
WAP
microbrowser
running on
WAP-enabled
devices
WAP
TCP/IP
HDML protocol WAP
/WML
gateway stack
stack
HTML
/XML
Web
server
WAP offers a small, extensible protocol stack to handle
mobile communications more efficiently.
XML — a powerful extensible alternative to HTML
WML — a small set of XML for wireless network
HDML — compact HTML for handheld devices
DISTRIBUTED SYSTEMS SERVE THE
ALWAYS-ON WORLD(Next-gen. Internet)
Limitations of current WAN:
◊
◊
◊
◊
do not deal with congestion effectively
poor support for QoS
low reliability
no clear definition of the semantics of shared state
Internet2 Project
◊
◊
◊
◊
◊
◊
High-speed gigapops at > 155 Mbps
vBNS at 622 Mbps - 2.4 Gbps
IP Multicast protocol and IPv6
Digital audio and video frameworks
QoS
Distributed storage management
NGI - a US government program along with
DISTRIBUTED SOFTWARE
DEVELOPMENT(Remote Method Invocation)
Remote object reference specifies the remote
object to receive RMI.
Remote interface provides a definition of the
methods available for RMI, same as using IDL.
Remote reference module translates b/w local
& remote object references & creates a table.
RMI compiler generates the proxy (one per
remote object), dispatcher and skeleton (for
each class of a remote object).
DISTRIBUTED SOFTWARE
DEVELOPMENT(Major Steps of a RMI )
1. invoke RMI via proxy for B.
2. martial arguments, call rrm to translate to remote object
3,4. Send the message and receive the message.
ref.
5. select the method in the skeleton.
6. call rrm to translate into remote object B, unmartial the arg.
1
Object A
remote
ref. module
2
6
2
Proxy for B
11
3
4
Comm.
module
Comm.
module
10
9
dispatcher
CLIENT
remote
ref. module
SERVER
6
5
Skeleton
for B
8
11
7. execute the method, return the result.
8. martial the result in a reply message.
9,10. send the message and receive the message.
11. call rrm for the object A, unmartial the result.
Object B
7
DISTRIBUTED SOFTWARE
DEVELOPMENT(Component-Based Development)
CBD — the 3rd “spark” of s/w development.
◊ to build s/w out of prepackaged components.
◊ S/w component — binary unit of independent
production, acquisition, and deployment.
◊ S/w comp. encapsulates state & functionality.
◊ A s/w component can be plugged into distributed applications in its predesigned form.
◊ S/w component has a behavior specification
as its formal description, that can be used
for the purpose of software verification.
◊ S/w component’s interface is defined by IDL.
DISTRIBUTED SOFTWARE
DEVELOPMENT(Motivation of CBD)
Motivation 1: emphasis on software reuse.
Motivation 2: success of the techniques for
building GUIs, DBs, … out of components.
Motivation 3: the push for interconnection
technologies: CORBA, DCOM, JavaBeans.
Motivation 4: generalization of object tech.
Motivation 5: high cost of monolithic products.
Motivation 6: The distributed computing model
fosters the development of s/w components.
DISTRIBUTED SOFTWARE
DEVELOPMENT(Characteristics of Component)
a well-defined, well-documented interface
defining the services the comp. provides
software independence from its clients
encapsulated implementation
remote access
reusability thru abstraction and encapsulation
characteristics of objects.
robustness:incorporate self-managing features,
comm. seamlessly via messaging protocols.
DISTRIBUTED SOFTWARE
DEVELOPMENT(Component Assembly)
Challenges of building component based DS:
not to change component’s source code
to maintain objects’ implicit dependencies
Solution: assembly approach separates
architecture, component, and distributed
object infrastructure concerns.
Architecture defines components in the sys.
Component view concerns comp. composition
and implementation.
Distributed object infrastructure view concerns
inter-comp. communication and protocols.
DISTRIBUTED SOFTWARE
DEVELOPMENT(JavaBeans used as component)
use ports and links to isolate core component
functions from inter-comm. mechanisms.
implement the framework using JavaBeans.
JavaBeans uses facilities for reflection:
dynamically discover an object’s structure
manipulate the object using information
extracted from its .class file
extend JavaBeans using SoftBeans to refer
to components.
A PortDescriptor class extends PropertyDescriptor class. A SoftBeanInfo interface
extends BeanInfo interface.
DISTRIBUTED SOFTWARE
DEVELOPMENT(JavaBeans component model)
Four elements define component’s boundary.
Service
provided
m
m
e
Events observed
Internal
component
Service
required
e
e
Events generated
e
m
m
m
e
Three component interaction styles:
• event-event:
publish event-listener registration and
event dispatch methods.
observe events by event-listener interface
• service-service
obtains svc required from svc provided.
• event-service
Event generated triggers service provided
DISTRIBUTED SOFTWARE
DEVELOPMENT(Ports and Links)
Port
ServicePort
EventPort
DiscreteServicePor
SessionServicePort
t
DiscreteServiceProvidePor
similar to
the left
tDiscreteServiceRequirePort
EventGeneratePort
EventObservePort
Link
ServiceLink
SessionServiceLink
EventLink
DiscreteServiceLin
k
LocalSessionServiceLink
IIOPServiceLink
RMISessionServiceLink
EventServiceLink
DISTRIBUTED SOFTWARE
DEVELOPMENT
(An Example applying the method to Shopper pattern)
RMIDiscreteServiceLink
IIOPDiscreteServiceLink
session
Shopper
m
getSuppiers(…)
m
Supplier
DB
m
Consumer
m
m
session
m
Warehouse
Store
shop(…)
m
discrete
buy(…)
buy(…)
Consumer
m
m
IIOPSessionServiceLink
LocalDiscreteServiceLink
discrete
getSuppiers(…)
e
Warehouse
shop(…)
lowSupply event
m
lowSupply event
principals
m
e
shop(…)
Store
getSupply(…)
m
getSupply(…)
sell(…)
RMIEventLink
m
Store
AssociatedStore
m
Store