CS502 - Computing and Communication Technology

Fall-2009

Prerequisites: Must be enrolled in graduate level

Description:  The course offers a comprehensive coverage of the basic concepts of computing and data technologies.  The first part of the course is devoted to the computer organization and design. This part discusses the main components of computers and the basic principles of their operation. It demonstrates the relationship between the software and hardware and focuses on the foundational concepts that are the basis for current computer design. The second part of the course discusses the architecture of the distributed computer systems. The main emphasis here is on data distribution, as the way data are generated, stored and used is naturally distributed. This part discusses various levels of transmitting, storing and using information, data and knowledge and surveys important areas as Information Theory, Switching, Databases, Data classification, Distributed memory and data retrieval, World Wide Web and Data Mining.

Course objectives: Upon successful completion of the course the student will be able to

• Understand the basics of the Von Neumann computing architecture
• Understand the basics of the MIPS instruction set architecture and write simple assembly language programs
• Design simple ALU and CPU at an abstract logical level
• Understand the principles of distributes systems and
• Understand the basics of important related areas as Information Theory, Switching, Databases, Information retrieval, World Wide Web and Data Mining

Required software: SPIM simulator: A free software simulator for running MIPS R2000 assembly language programs available for Unix, DOS, and Windows.

WEB resources:

• Publishers Web page of the Hennessy & Patterson Computer Organization and Design: The Hardware/Software Interface, Fourth Edition
• Companion Web Site for Computer Organization and Design
• SPIM simulator: A free software simulator for running MIPS R2000 assembly language programs available for Unix, DOS, and Windows.
• MIPS Web Site
• Andrew S. Tanenbaum, Maarten van Steen, Distributed Systems: Principles and Paradigms
• Book website
• Chapter-1 PPT slides
• The Modern History of Computing
• John von Neumann
• Information Retrieval Resources and Demos
• The Web
• The World Wide Web Consortium
• Semantic Web
• International Semantic Web Conference (ISWC)
• The DARPA Agent Markup Language Homepage
• SemanticWeb.org
• Semantic Web History: Nodes and Arcs 1989-1999
• Professor James A. Hendler
• Data/Web Mining
• KD Nuggets Directory
• Weka 3 -- Machine Learning Software in Java
• Zdravko Markov and Daniel T. Larose: Data Mining the Web: Uncovering Patterns in Web Content, Structure, and Usage, Wiley, April 2007
• Jiawei Han and Micheline Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers, 2000
• Software for Data Mining / Web Mining
• Web->KB project
• WinMine Toolkit Home Page
• Microsoft Bayesian Network

Assignments, projects and grading: There will be a mid-term test, a mid-term project and a term paper. There will be also a programming assignment and a quiz. The final grade will be based 40% on the term paper, 30% on the mid-term project, 20% on the test, 5% on the programming assignment and 5% on the quiz. The letter grades will be calculated according to the following table:
 

A	A-	B+	B	B-	C+	C	C-	D+	D	D-	F
95-100	90-94	87-89	84-86	80-83	77-79	74-76	70-73	67-69	64-66	60-63	0-59

All assignments with their due dates are listed below (the project descriptions are given on separate pages) and must be submitted through Blackboard Vista available through CentralPipeline (Student > Blackboard Vista > CS 502) or directly at https://vista.csus.ct.edu/webct/logon/459901950011

Unexcused late submission policy: Assignments submitted more than two days after the due date will be graded one letter grade down. Projects submitted more than a week late will receive two letter grades down. No submissions will be accepted more than two weeks after the due date.

Tentative schedule of classes (weeks) and assignments

NOTE THAT THE MATERIAL FOR WEEKS 1-6 WILL BE UPDATED TO REFLECT THE NEW EDITION OF THE BOOK

1. September 1-3: Computer instruction set architecture
2. September 8-10: Computer arithmetic and the ALU design
3. September 17: Programming assignment due
4. September 29 - October 1: CPU datapath and control
5. October 6 - 8: Pipelining
6. October 15: Building a 16-bit ALU (part of the Midterm Project) due.
7. October 20 - 22:  Memory hierarchies
8. October 27 - 29:  Interfacing peripherals and multiprocessors
9. October 29:  Midterm Project due
10. October 27:  Mid-term test. To be taken online through Blackboard Vista
11. Fundamentals of distributed systems
12. Information Theory
13. Switching
14. Database management concepts
15. Distributed memory and data retrieval
16. Quiz.due. Week topic: The World Wide Web
17. Introduction to Data Mining
18. Term paper due

CS502 - Week 1

Computer Architecture = Instruction Set Architecture + Machine Organization

Lecture Slides: PDF

Lecture Notes:

1. Levels of Abstraction
• Software:
• Application
• Operating System
• Firmware
• Instruction Set Architecture:
• Organization of Programmable Storage
• Data type and Structures: encodings and machine representation
• Instruction set
• Instruction Formats
• Addressing Modes and Accessing Data and Instructions
• Exception Handling
• Hardware:
• Instruction Set Processing
• I/O System
• Digital Design
• Circuit Design
• Layout
2. Basic Components of a Computer
• Processor: Datapath and Control
• Memory
• I/O
3. Example: implementing A=B+C (from instructions to gates)
4. MIPS instructions
• Arithmetic
• Memory organization and load and store
• Instruction types and formats
• R-type
• I-type for arithmetic
• I-type for lw and sw
• I-type for branch
5. Stored program concept: programs in memory, fetch&execute cycle
• Von Neumann Architecture
• CPU, Memory System, I/O system
• Stored program concept: programs in memory, fetch&execute cycle
• Instructions are executed sequentially
• Turing machines
• Alan Turing web page
• Turing machines
• A Turing Machine Applet
• Non-Von Neumann Architecture:
• Various parallel and multiprocessor architectures (see Fundamentals of distributed systems)
• In broader sense: NN, GA etc.
• The Modern History of Computing
• John von Neumann
6. The SPIM simulator

CS502 - Week 2

Computer arithmetic and ALU design

Lecture Slides (PDF), ALU diagram (PDF)

Lecture Notes:

1. Representing numbers: sign bit, one's complement, two's complement.
2. Arithmetic: addition, subtraction, detecting overflow.
3. Building ALU - hierarchical approach
4. Floating point numbers
• Scientific notation: (-1)^sign * significand * 2^exponent
• Range and precision (overflow and underflow).
• IEEE 754 floating point standard - allows integer comparison:
• normalized representation
• implicit leading 1
• exponent is biased: exponent in [0..0 (most negative), 1..1 (most positive)]
• bits of the significand represent the fraction between 0 and 1.
• (-1)^S * (1 + s1*2^-1 + s2*2^-2 + ...) * 2^(exponent-bias)
• Problems with floating point arithmetic

• Two’s complement numbers:
http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_1.html (tutorial)
http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08quiz.html (quiz)
• Floating point:
http://chortle.ccsu.edu/AssemblyTutorial/Chapter-30/ass30_1.html (tutorial)
http://chortle.ccsu.edu/AssemblyTutorial/Chapter-30/ass30quiz.html (quiz)

CS502 - Week 3

CPU datapath and control

Lecture Slides: PDF

Lecture Notes:

I. Building a Datapath

1. Abstract level implementation:
• Instruction memory
• Program counter
• Register file
• ALU
• Data memory
2. Basic building elements
• Combinational logic (e.g. ALU)
• State elements (registers, memory)
• Clocking methodology: edge triggered
3. Fetching instructions and incrementing the program counter
4. Register file and execution of R-type instructions
5. Datapath for lw and sw instructions (add data memory and sign extend)
6. Datapath for branch instructions

• http://www.it.jcu.edu.au/Subjects/cp2005/resources/animation/wk6animations.ppt (if it does not work try it in Blackboard Vista)
• http://www.web-ee.com/primers/files/MIPS/MIPS.htm
• https://www.cs.tcd.ie/Jeremy.Jones/vivio/dlx/showanim.php?name=Tutorial01

1. ALU control: mapping the opcode and function bits to the ALU control inputs
2. Designing the main control unit
3. Operation of the Datapath (single-cycle implementation):
• R-type instructions
• Load (store) word
• Branching instructions
4. Problems of the single-cycle implementation

CS502 - Week 4

Pipelining

Lecture Slides: PDF

Lecture notes:

I. Introduction to Pipelining

1. Pipelining by analogy (laundry example):
• Pipelining helps throughput of the entire workload
• Multiple tasks operating simultaneously and using different resources
• Potential speedup = number of pipe stages
• The pipeline rate is limited by the slowest stage
• Unbalanced lengths of pipe stages reduces the speedup
• The time to "fill" the pipeline and the time "drain" it reduces the speedup
• Stall for dependencies
2. Five stages of the load MIPS instruction
• Insturction fetch.
• Instruction decode.
• Execute (ALU operation).
• Memory access.
• Write back (register write).
3. The pipelined datapath
4. Single cycle, multiple cycle vs. pipeline
5. Advantages of pipelined execution

1. Structural hazards: single memory
2. Control hazards:
• Stall: wait until decision is clear
• Predict: fixed prediction (e.g. fail), dynamic prediction (based on history)
• Delayed brach (software solution):

add $4, $5, $6            beq $1, $2, $40
beq $1, $2, 40     ==>    add $4, $5, $6
lw $3, 300($0)            lw $3, 300($0)
3. Data hazards (dependecies backwards in time):
• Forwarding (bypassing - hardware solution)
• Reordering code (software solution)

lw $t0, 0($t1)               lw $t0, 0($t1)
lw $t2, 4($t1)      ==>      lw $t2, 4($t1)
sw $t2, 0($t1)               sw $t0, 4($t1)
sw $t0, 4($t1)               sw $t2, 0($t1)

• http://www.web-ee.com/primers/files/MIPS/MIPS.htm
• https://www.cs.tcd.ie/Jeremy.Jones/vivio/dlx/showanim.php?name=Tutorial09

CS502 - Week 5

Memory hierarchies

Lecture Slides: PDF

Lecture notes:

1. Memory technologies and trends
2. Impact on performance
3. The need of hierarchical memory organization
4. The principle of locality
5. Memory hierarchy terminology
6. The Basics of caches
• Direct-mapped cache: Accessing a cache (Cash index,Tag,Valid bit)
• Writing to the cache (write-through and write-back schemes)
• Improving cache performance by flexible placement of blocks in the cache (slides in PS, slides in PDF)
• Direct mapped: Cache index = (Block address) modulo (Cache size); no search; small tag.
• Set associative: Cache index = (Block address) modulo (Number of sets in cache); search the set; larger tag.
• Fully associative: Cache index is not determined; search the whole cache; tag = address.
• Choosing which block to replace: least recently used
7. The need of virtual memory
• Many programs (processes) can use a single memory
• Use a memory exceeding the size of the main memory
8. VM organization and terminology: virtual address, physical address, page, page offset, page fault, memory mapping (translation).
9. Addressing pages:
• Page table, page table register
• Processes (active, inactive) and page tables
• Page faults
• Replacing pages: LRU, reference (use) bit
• Write-back scheme (dirty bit)

CS502 - Week 6

Interfacing peripherals and multiprocessors

Lecture Slides: Chapter7.pdf

Lecture notes:

1. Interfacing Processors and Peripherals - Buses (slides in PDF)
• Buses: lines, transactions, types
• Synchronous and asynchronous buses
• Handshaking protocol
• Bus access: master and slave
• Bus arbitration schemes
• Bus standards
2. Interfacing I/O devices to Memory, CPU and OS (slides in PDF)
• The role of the operating system in interfacing I/O devices to Memory
• Controlling the I/O devices
• Memory mapped I/O
• Special I/O instructions
• Communicating with the processor
• Polling
• Interrupt-driven I/O
• Direct memory access (DMA)
3. Multiprocessors (slides in PDF)
• Basic approaches to sharing data and types of connectivity
• Programming multiprocessors
• Multiprocessors connected by a single bus
• A parallel program
• Multiprocessor cache coherency
• Implementing a multiprocessor cache coherency protocol
• Synchronization using coherency
4. Networks of muiltiprocessors (slides in PDF)
• Shared memory vs. multiple private memories
• Centralized memory vs. distributed memory
• Parallel programming by message passing
• Distributed memory communication
• Memory allocation
• Clusters and network topology
5. Modern clusters
• The Beowulf Project
• AppleSeed Project
• Writing Parallel Programs using MPI

CS502 - Week 7

Fundamentals of distributed systems

• Book website
• Chapter-1 PPT slides

1. Categories of computer systems
• Conventional sequential machines (mainframes, minicomputers +  network of terminals) - multitasking, multiusers.
• Conventional systems with special purpose components (specialized processors) - single specialized task.
• Multiprocessor systems - single task allowing parallel computation.
• Distributed systems (computers connected by a network) - different task, shared data.
2. Conventional systems with special purpose components
• A special purpose unit (e.g. math processor) attached to the main bus
•  Back-end system (additional separate machine, e.g. graphic terminal)
•  Example: iDBP
•  file operations: positioning and manipulating a cursor in a file
•  used to implement relational database systems
•  add-on board or back-end system
3. Multiprocessor systems:
• Multiple processors
• Shared memory (single address space) vs. multiple private memories
• Centralized memory vs. distributed memory
• Categories of parallelism:
• Single instruction stream, single data stream (SISD)
• Single instruction stream, multiple data streams (SIMD)
• Multiple instruction streams, single data stream (MISD)
• Multiple instruction streams, multiple data streams (MIMD)
4. Distributed computer systems
• Issues:
• data location and security
• load distribution
• process migration
• fault tolerance
• Types:
• homogeneous systems
• heterogeneous systems
• Distributed file systems:
• NFS (UNIX, DOS, system independence)
• The Coda Distributed File System
• Fault-tolerant networks:
• redundancy (static-masking, dynamic)
• consistency (strong, weak)
• Firewalls and self-stabilizing networks

CS502 - Week 8

Information Theory

1. Fundamentals of information theory (information vs. data)
• Probability (see http://mathworld.wolfram.com/Probability.html)
• Frequency approach - experiments
• Objective approach - properties real world entities
• Subjective approach - the uncertainty of the agent (agent's knowledge)
• Example: the probability that the sun will rise tomorrow - undefined, 1, 1-e, Laplas estimate: (d+1)/(d+2); Laplas for k-outcomes: (n+1)/(N+k)
• Joint probability: P(A.B)=P(A)*P(B) (if A and B are independent)
• Conditional probability: P(A.B)=P(A|B)*P(B)
• Bayes Theorem (more in PDF): P(A|B)=P(B|A)*P(A)/P(B)
• Interpretation of Bayes: A - cause; B - effect; posterior=likelihood*prior/evidence
• Law of total probability: A={A1,A2,...An}, exhaustive, mutually exclusive (P(Ai.Aj)=0;i\==j); P(B)=SUM P(B|Ai)P(Ai)
• Claude Shannon (see http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html)
• Measuring information
• Settings: source, message, recipient
• Recipient's point of view: a measure of uncertainty, expected surprise of getting the message
• Basic formula: I(M)=-P(M) or I(M)=-log2P(M) (minimal number of bits to encode the message)
• Logarithmic scale: additivity: I(M1)+I(M2)=-logP(M1)-logP(M2)=-log(P(M1)P(M2))=I(M1 and M2)
• Log 2 scale: reducing the uncertainty (halving strategy, guess a number in [0,7]), measuring unit: bit
• Entropy (average information): uncertainty of the recipient, the expected surprise of getting an arbitrary message from a set of possible messages.
• H=-P1.logP1-P2.logP2-...-Pn.logPn
• P1+P2+...+Pn=1
• Example1: H({A,~A})=-P(A).logP(A)-P(~A).logP(~A). Maximum for P(A)=1/2, minimum for P(A)=1
• Example2: X={0,1,...,7}, P(X=1)=P(X=2)=...=p(X=7)=1/8; H(X)=-8*(1/8)*log(1/8)=3 (bits)
2. Sampling Theorem
• Representing signals: frequency, time, amplitude
• Baseband signals: F(t) limited in frequency in the interval [-W,W]
• Broadband signals (carrier based):  moved in the interval [Wc-W,Wc+W], e.g. F(t)=Fs(t)sin(Wct)
• Representing signal by sample points (theoretically, infinite number of points required)
• locating a point in space: coordinate systems
• locating a function F(t) : vector (F(t1),F(t2),...,F(tn)), tn - sample points
• orthonormal sets of functions: Integral(a,b) Gn(x)Gm(x)dx = {1 for n=m; 0 for n\=m}
• expansion of a function (Fourier series): F(x)=Sum(n=-inf, n=+inf)CnGn(x), Cm=Integral(-inf,+inf) F(x)Gm(x)dx
• Sampling theorem (see also http://mathworld.wolfram.com/SamplingTheorem.html)
• {Sincn(t)} in [-T,T], T-> +inf; Sincn(t)=sin(2piW(t-n/(2W))/2piW(t-n/(2W)
• F(t)=Sum(n=-inf, n=+inf) Cn sin(2piW(t-n/(2W))/2piW(t-n/(2W)
• F(tn)=Cn (all terms above are 0 except one, sin(0)/0=1)
• F(t)=Sum(n=-inf, n=+inf) F(tn)sin(2piW(t-tn)/2piW(t-tn), tn=n/(2W) (sampling theorem)
• constraints: F(t) is limited in frequency in [-W,W], infinite time duration (infinite number of sample points)
• AD and DA conversion: quantization (thresholds), amplifiers vs. repeaters, generally very low error rates (regenerating digital values at relay points)
• Error detection and correction
• Binary case: {000,111} for {0,1} - one error correcting code
• Arbitrary waveform: three instead of one sample point - widening the bandwidth (2TW dimensions)
• Demonstration Applets from Information Technology: Inside and Outside by David Cyganski, John A. Orr with Richard F. Vaz.

CS502 - Week 9

Switching

1. The importance of switching in communication - the cost of switching is high
2. Definition: transfer input sample points to the correct output ports at the correct time
3. Terminology
• Switching
• Digital switching (sample points amplitudes are 0's and 1's)
• PABX
• Circuit
• Circuit switching
• Packet switching
4. Voice digitization: W=3KHz, sampling at 2*3=6 or 8KHz, 256 levels for quantization (8 bits), Bit rate=64Kb/s
5. Telephone switching
• Time division multiplexing: time slot (0.1 ms), field, frame; 125ms/0.8=150 channels + time for synchronization and control
• Switch architecture
• Sampling input signals, storing values in memory, placing values in the proper field and frame of the output sequence
• Need for more channels: hierarchical switching
• Combining time and space switching
6. General framework for switching
• time, space and frequency (broadband signals) switching
• synchronization (single clock) and buffering (memory)
• set-up time and delay (propagation time)
• "call duration" assignment vs. dynamic assignment
• in-band and out-of-band signaling
7. Circuit (synchronous) vs. packet (asynchronous) switching: control and routing overhead, virtual packet switching
8. Switching techniques and networking: switching is the technology allowing to get a message between the nodes of a network
• Crossbar switching: mechanical (in the past) or electronic.
• Bus and cable switches: computer buses or cables (switching + transportation = network)
• Token passing approach (similar to the locks used by multiprocessors connected by a bus)
• Ethernet approach: cable or ring, packets, conflicts, resending
• Synchronization and Hub switch: star networks (no conflicts)

CS502 - Week 10

Database management concepts

1. Database Management Systems (DBMS)
• Managing large quantity of structured data
• Efficient retrieval and modification: query processing and optimization
• Sharing data: multiple users use and manipulate data
• Controlling the access to data: maintaining the data integrity
2. An example of a database (relational): relations (tables), attributes (columns), tuples (rows). Example query: Salesperson='Mary' AND Price>100.
3. Database schema (e.g. relational): names and types of attributes, addresses, indexing, statistics, authorization rules to access data etc.
4. Data independence: separation of the physical and logical data (particularly important for distributed systems). The mapping between them is provided by the schema.
5. Architecture of a DBMS - three levels: external, conceptual and internal schema
6. Types of DBMS
• The data structures supported: tables (relational), trees, networks, objects
• Type of service provided: high level query language, programming primitives etc.
7. Basic DBMS types
• Linear files
• Sequence of records with a fixed format usually stored on a single file
• Limitation: single file
• Example query: Salesperson='Mary' AND Price>100
• Hierarchical structure
• Trees of records: one-to-many relationships
• Limitations. ITEM-SUPPLIER: many-to-many relationship (requires duplicating records);  problems when updated
• Retrieval requires knowing the structure (limited data independence): traversing the tree from top to bottom using a procedural language
• Network structure
• Similar to the hierarchical database with the implementation of many-to-many relationships
• Record and set types
• Relational structure
• Relations, attributes, tuples
• Primary key (unique combination of attributes for each tuple)
• Foreign keys: relationships between tuples (many-to-many). Example: SUPPLIES defines relations between ITEM and SUPPLIER tuples.
• Advantages: many-to-many relationships, high level declarative query language (e.g. SQL)
• SQL example (retrieve all items supplied by a supplier located in Troy):

SELECT ItemName
FROM ITEM, SUPPLIES, SUPPLIER
WHERE SUPPLIER.City = "Troy" AND
      SUPPLIER.Supplier# = SUPPLIES.Supplier# AND
      SUPPLIES.Item# = ITEM.Item#
• Programming language interfaces: including SQL queries in the code
• Object-Oriented structure
• Objects (collection of data items and procedures) and interactions between them.
• Is this really a new paradigm, or a special case of network structure?
• Separate implementation vs. implementation on top of a RDBMS
8. Retrieving and manipulating data: query processing
• Parsing and validating a query: data dictionary - a relation listing all relations and relations listing the attributes
• Plans for computing the query: list of possible way to execute the query, estimated cost for each. Example:
SELECT ItemNames, Price
FROM ITEM, SALES
WHERE SALES.Item# = ITEM.Item# AND Salesperson="Mary"
• Index: B-tree index, drawbacks - additional space, updating; indexing not all relations (e.g. the keys only)
• Estimating the cost for computing a query: size of the relation, existence/size of the idices.Example: estimating Attribute=value with a given number of tuples and the size of the index.
• Query optimization: finding the best plan (minimizing the computational cost and the size of the intermediate results), subsets of tuples, projection and join.
• Static and dynamic optimization
9. Database views: creating user defined subsets of the database, improving the user interface. Example:
CREATE VIEW MarySales(ItemName,Price)
AS SELECT ItemName, Price
FROM ITEM, SALES
WHERE ITEM.Item#=SALES.Item# AND Salesperson="Mary"

Then the query:

SELECT ItemName
FROM MarySales
WHERE Proce>100

translates to:

SELECT ItemName
FROM ITEM, SALES
WHERE ITEM.Item#=SALES.Item# AND Salesperson="Mary" AND Price>100
 

10. Data integrity
• Integrity constraints: semantic conditions on the data
• Individual constraints on data items
• Uniqueness of the primary keys
• Dependencies between relations
• Concurrency control
• Steps in executing a query.
• Concurrent users of the database, interfering the execution of one query by another
• Transaction: a set of operations that takes the database from one consistent state to another
• Solving the concurrency control problem: making transactions atomic operations (one at a time)
• Concurrent transactions: serializability theory (two-phase locking), read lock (many), write lock (one).
• Seriazible transactions: first phase - accumulating locks, second phase - releasing locks.
• Deadlocks: deadlock detection algorithms.
• Distributed execution problems: release a lock at one node (all locks accumulated at the other node?); strict two-phase locking
• Backup and recovery
• The problem of keeping a transaction atomic: successful or failed (What if some of the intermediate steps failed)
• Log of database activity: use the log to undo a failed transaction.
• More problems: when to write the log, failure of the recovery system executing the log.
• Security and access control
• Access rules for relations or attributes. Stored in a special relation (part of the data dictionary).
• Content-independent and content-dependent access control
• Content-dependent control: access to a view only or query modification(e.g. and-ing a predicate to the WHERE clause)
• Discretionary and mandatory access control
11. Client-Server architectures
12. Knowledge Bases and KBS (and area of AI)
• Information, Data, Knowledge (data in a form that allows reasoning)
• Basic components of a KBS
• Knowledge base
• Inference (reasoning)  mechanism (e.g. forward/backward chaining)
• Explanation mechanism/Interface
• Rule-based systems (medical diagnostics, credit evaluation etc.)

CS502 - Week 11

Distributed memory and data/informition retrieval

1. The need of memory hierarchy
• Massive data storage requirements (e.g. a satellite orbiting Earth generates 1 terabyte data per day)
• Difference in the cost and capacity of different types of memory
• Data location
2. Data location factors
• Cost
• Performance
• Reliability
• Application software
3. Directory - a mechanism to locate a data object
• Directory location: may be different from the data location
• Directory server: a separate system, not a part of the application program
• Directory structure: usually hierarchical
• Directory search: finding out the data location and making use of this fact (e.g. designing an application)
• Providing access control
4. Directory systems
• Pure approaches
• Master control directory: a single directory containing all the information
• Directory server: a single computer providing all directory functions (contains the master directory)
• Fully replicated directories: copies of the directory at different locations (concurrency control required)
• Local directories: contain information on local data and usually stored at the same location
• Point of control directories: located at the point where the access control is exercised (e.g. hard disk)
• Problems with scaling: hierarchical system of directories (different directories at different levels)
• Important issues
• Directory backup
• Coherency and consistency
• Local caching
5. Directories and access control (different functions). Points of access control
1. Application program (problems with using data provided by other applications)
2. DBMS (the most common approach)
3. Control at the physical location of data (e.g. library)
4. Function of the communication networks (e.g. preventing a user from accessing another node, telephone system)
6. Information retrieval (Slides in PPT)
• Basics
• Finding relevant data using irrelevant keys
• Example: database of photographic images sorted by number, date.
• DBMS: Well structured data according to the information content
• Text document retrieval (not well structured data)
• Document retrieval queries
• NLP: requires structured data to match the translated query
• Keyword search: boolean, weighted
• Abstracting documents
• Evaluating retrieval quality
• Precision: retrieved and relevant /retrieved
• Recall: retrieved and relevant /relevant
• Access methods
• Full text scanning:  hardware support
• Keyword or phrase indexing: storage overhead (average 30%-70%), index updating
• Document signature: a fixed length bit string for each document (precision and recall easily computed)
• Information Retrieval Resources and Demos: http://ir.exp.sis.pitt.edu/resources/
7. Web document retrieval
• Crawling the Web
• Web Crawler Example: WebSPHINX: A Personal, Customizable Web Crawler
• Example of running a Web Crawler
• W3C Protocol Library
• Analyzing the Web structure
• Social Networks
• Page Rank
• Authorities and Hubs
• Web document retrieval books and atricles
• Data Mining the Web: Uncovering Patterns in Web Content, Structure, and Usage, Chapters 1, 2
• Mining the Web: Discovering Knowledge from Hypertext Data, Chapters 7, 8.
• The PageRank Citation Ranking: Bringing Order to the Web by Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. Stanford Digital Library Technology Project, 1998
• Authoritative Sources in a Hyperlinked Environment Jon M. Kleinberg. Journal of the ACM 46:5 pp. 604-632, 1999
8. Document classification and clustering:
• Document attributes: semantic (NLP, domain knowledge), statistical (keyword frequencies, vector space model, TFIDF), mixed
• Similarity measures: cosine similarity, distance, information compression metrics
• The Machine Learning approach
• Introductory book chapter: Chris Thornton, Truth from Trash:How Learning Makes Sense, MIT Press, 2000
• Illustrative example: Web/text document classification (files: textmine.pl, webdata.zip, artsci.pl)
• Using the Weka Data Mining System
• Introduction to Machine Learning
• Classification/Prediction task: Play Tennis example
• Bayesian text classification (reading: Tom Mitchell, Machine Learning, McGraw Hill, 1997)
• Bayes theorem
• Naive Bayes algorithm
• Learning to classify text
• Clustering algorithms (reading: A Comparison of Document Clustering Techniques)
• Flat clustering: cluster and centroid (typical cluster document), k-means algorithm
• Hierarchical clustering (example Dendrogram)
9. Web Mining
• Web content mining - discovery of Web document content patterns (text mining).
• Web structure mining - discovery of hypertext/linking structure patterns
• use hyperlinks to enhance text classification
• page ranking
• modeling and measuring the Web
• Web usage mining - discovery of web users activity patterns
• mining web server logs
• mining client machine access logs
10. Web Mining books
• Data Mining the Web: Uncovering Patterns in Web Content, Structure, and Usage
• Mining the Web: Discovering Knowledge from Hypertext Data

CS502 - Week 12

The World Wide Web

1. A little history
• 1989, CERN: distribution of linked documents (nuclear physics)
• 1991, text-based prototype
• 1993, First graphical interface - Mosaic
• 1994: WWW consortium (CERN, MIT): http://www.w3.org
2. The client side
• WEB documents (pages) connected via hyperlinks (hypertext).
• Hyperlinks: highlighted strings in text or images.
• Browsers (text-based or graphical): tools for navigating the WEB.
• Forms and Java applets
3. The server side
• URL (Uniform Resource Locator): <protocol name>://<machine name>/<file name>, e.g. http://www.w3.org/History.html
• Steps of fetching http://www.w3.org/History.html
• The browser determines the URL
• The browser asks the local DNS (Domain Name System) server for the IP (Internet Protocol) address
• DNS replies with 18.23.0.23.
• The browser makes a TCP (Transmission Control Protocol) connection to port 80 on 18.23.0.23
• It then sends a GET /hypertext/WWW/History.html
• The www.w3.org server send the file History.html
• The TCP connection is released
• The browser displays all the text in History.html
• The browser displays all the images in History.html (new TCP connection for each image)
• Example of HTTP protocol in text:

C: telnet www.w3.org 80
T: Trying 18.23.0.23 ...
T: Connected to www.w3.org
T: Escape character is '^]'
C: GET /hypertext/WWW/TheProject.html HTTP/1.0
    HTTP/1.0 200 Document follows
    MIME-Version: 1.0
    Server: CERN/3.0
    Content-Type: text/html
    Content-Length: 8247

    <HEAD><TITLE> The World Wide Web Consortium (W3C)</TITLE><HEAD>
    <BODY>
    <H1><IMG ALIGN=MIDDLE ALT="W3C" SRC="Icons/WWW/w3c_main.gif">
    The World Wide Web Consortium </H><P>

    The World Wide Web is the universe of network-accessible information.
    ...
    </BODY>
 

• Using other protocols
• HTTP Browser <---> FTP server
• HTTP Browser <---> FTP Proxy server <---> FTP server
• Proxy servers: translating protocols, caching pages, filtering information
• HyperText Transfer Protocol (HTTP)
• Simple (GET without the protocol version) and full requests
• Methods (commands)
• GET: request to read a Web page encoded in MIME (Multipurpose Internet Mail Extensions - adding a header to describe the encoding)
• HEAD: request to read a Web page header
• PUT: request to store a Web page (may include authentication headers)
• POST: request to append new data to a Web page (e.g. posting a message to a news group)
• DELETE: request to delete a Web page (may include authentication headers)
• LINK: Connects two existing pages
• UNLINK: breaks an existing connection between two pages
4. Writing WB page in HTML
• URL (Universal Resource Locator): a mechanism for naming and locating Web pages
• <Protocol>://<DNS name of the host>/<File name (with possible shortcuts, e.g. ~user)>
• Protocols:
• HTTP. e.g. http://www.cs.ccsu.edu/~markov/
• FTP (File Transfer Protocol), e.g. ftp://cs.ccsu.edu/
• File: accessing a local file, e.g. /usr/pages/mypage.html
• Mailto (sending an e-mail from a Web browser), e.g. mailto:markovz@ccsu.edu
• Telnet (establish an on-line connection to a remote machine), e.g. telnet://cs.ccsu.ctstateu.edu/
• The HTML language
• Standardized markup language: how the documents are to be formatted and reformatted (e.g. LaTeX), contrasted to WYSIWYG (not standardized, does not allow reformatting)
• Tags with parameters, e.g. <IMG SRC ="http://www.widget.com/image.gif" ALT="AWI Logo">
• Hyperlinks:
• <A HREF="http://www.nasa.gov"> NASA's home page </A>
• <A HREF="http://www.nasa.gov"> <IMG SRC="shuttle.gif" ALT="NASA"> </A>
• Forms (HTML 2.0): two-way trafic between the page owner and page user, <INPUT> tag. Example: Look-Up Classes
• CGI (Common Gateway Interface): a standard for handling forms' data. Example: interfacing a database:
• Write a script (program) to interface between a database and the Web
• Store the script in the cgi-bin directory under an URL.
• When retrieves a page located in cgi-bin the HTTP server executes the script.
• Put the script name in the ACTION parameter of the form.
• The browser invokes the operation specified in METHOD (usually POST)
• The script is started and presented with the form input data.
• After the database retrieval the script produce an HTML file, which is sent back to the browser.
• This mechanism can be used to include selected ads in the Web page depending on what the user is looking for.
5. Java
• Applets
• Implementing highly interactive Web pages
• Running applications and using remote servers or databases
• Adding animation and sound to the Web page without spawning and external viewer
• No need of standard for the Web protocols (HTTP, FTP etc.)
• The Java system for the Web
• A Java-to-bytecode compiler
• A browser that understands applets (<APPLET> tag)
• A bytecode interpreter
• Security issues
• Problem: running a program on the client's machine (possible crash, collecting private information, consuming resources)
• Solutions:
• First barrier: strong typed language - array bounds checking, no pointers (thus no memory access)
• Second barrier: bytecode verifier
• Third barrier: class loader (loading first system classes before looking for user classes)
• Fourth barrier: security measures built in the classes, e.g. file access class (asking user if the applet needs file access).
• More problems:
• asking to access the /tmp directory
• requiring network access to work
• covert channels
6. Locating information on the Web
• The Web Challenges (How to turn the web data into web knowledge)
• Web Search Engines
• Topic Directories
• Semantic Web
• Crawling the Web
• Example: WebSPHINX: A Personal, Customizable Web Crawler
• Example of running a Web Crawler
• W3C Protocol Library
• Information Retrieval and Web Search
• Information Retrival (IR resources and demos: http://ir.exp.sis.pitt.edu/resources/)
• Information Retrieval and Web Search - Chapter 1 from Data Mining the Web: Uncovering Patterns in Web Content, Structure, and Usage by Zdravko Markov and Daniel T. Larose, Wiley, 2007.
7. Web Agents
• Is There an Intelligent Agent in Your Future?
• A good internet agent needs to be:
• Communicative: able to understand your goals, preferences and constraints.
• Capable: able to take options rather than simply provide advice.
• Autonomous: able to act without the user being in control the whole time.
• Adaptive: able to learn from experience about both its tasks and about its users preferences.
• Agent research sites:
• The UMBC Agent Web
• The National Research Council of Canada Agent resource list
• The European Community Agentlink project
• The University of Washington "Softbots" Project
• The MIT Media Laboratory Agents Research group
• Information Agents Research Group at the University of Southern California, Information Sciences Institute
8. Semantic Web
• Semantic Web Home Page
• The W3C Semantic Web Activity
• The DARPA Agent Markup Language (DAML)
• An example of a semantic web page
• Web Ontology
• A Web Ontology example
• Resource Description Framework (RDF)
• RDF Example: WWW Proposal

MIPS Programming assignment

Due date: September 17

1. At least one instruction from each instruction type: R-type arithmetic, I-type arithmetic and Memory transfer.
2. Input and output through system calls.
3. Comments explaining the format and the meaning of each instruction.

Documentation and submission: Submit the source text of the program as a file attachment through Blackboard Vista > CS 502 > MIPS Programming Assignment.

Mid-term test

The test includes the following topics:

• Number systems (binary,  hexadecimal, two's complements, floating point)
• MIPS instruction set architecture
• Single cycle datapath and control
• Basic principles of the pipelined datapath
• Identifying dependencies, and solving pipeline hazards
• Memory hierarchy (principles of caches)

Building a 16-bit ALU

Due date: October 15

Along with the Result output (delivering the result of the operation) the ALU must have the following additional outputs:

• One-bit  Zero output which is set to 1 when all bits of the Result are 0.
• One-bit Overflow output which is set to 1 when an arithmetic overflow occurs. Note that the non-arithmetic operations should not set the overflow bit. Use a box for the overflow block diagram showing only the inputs and the out and describe separately its logic by a truth table.

Documentation and submission: Write a report containing descriptive text, the ALU function code table, the overflow truth table, the 1-bit ALU diagram and the 16-bit ALU diagram. Use MS Word, PDF or HTML format. Submit your report as a file attachment through CCSU Pipeline > Student > Blackboard Vista > CS-502 > ALU Assignment. The maximum grade for this assignment is 10 points (1/3 of the Midterm Project grade).

Mid-term project (30 ponits): Designing a mini MIPS machine

Due date: October 29

The machine should have the following components (described as blocks with proper inputs and outputs):

1. General purpose registers (register file): 4 registers, 16-bit long, numbered 0 - 3.
2. Other registers: Program counter (16 bits).
3. Instruction Memory: Byte addressing, 16-bit word and 16-bit address.
4. Data Memory: Byte addressing, 16-bit word and 16-bit address.
5. ALU: 16 bit (include the assignment for week #5 described here).
6. Main control unit (include a truth table).
7. Other components necessary to connect the main components: sign extend, shift unit, multiplexes, gates (for the branch logic).

For the meaning of the instructions see the Patterson & Hennessy's text.

Instruction formats:

R-format (add, sub, and, or, rol)

op	rs	rt	rd	unused
4	2	2	2	6

I-format (lw, sw, beq, bne, addi)

op	rs	rt	address/offset/value
4	2	2	8

The project report should include the following:

1. Student name and project title
2. A descriptive text outlining the design of the machine (instruction set architecture, main components);
3. A description of the 16-bit ALU including a descriptive text and diagrams (include your report for the ALU assignment or a reference to it);
4. A diagram showing the datapath and control including all data and control lines marked with their width (number of bits);
5. A table describing the input/output behavior of the main control unit.

Extra credit (maximum 10% of the project grade): Implementing additional MIPS instructions, which require changes both in the diagram and in the control table.

Term paper (40 points)

Write a paper that analyzes a particular distributed computing environment. Examples of such environments are: a company computer and/or telephone network, a university campus network, hospital computer network, library network, ticket reservation system etc. Choose an environment that you know best and that is rich enough so that you can cover all of the following issues (including the sub items):

1. General description (describe the environment in general terms, i.e. the name/type and location of the network, who are the users and for what purpose it is used, what is the general structure etc.)
2. General requirements for the distributed system architecture to be used (in terms of cost, efficiency, security etc.).
3. Description of the distributed system architecture currently being used
• Sources and nature of information and data (voice, image, computer data files etc.)
• Basic characteristic of the data (location/distribution, media, volume, access/security)
• Database and/or information systems
• Computing resources: computers (conventional, specialized, multiprocessors) and other information processing equipment
• Switching and network technology
• Signals and communication channels (analog/digital, bandwidth, AD/DA conversion)
4. Problems with the current distributed system architecture (requirements that are not met, inadequate resources or technology)
5. Suggestions for improvement of the existing system architecture or brief description of a new architecture to meet the requirement

Format of the term paper

Policy on copying

Term paper grading

Submission

Extra credit

Quiz (max grade 5 pts.)