Trident tutorial
Trident is a high-level abstraction for doing realtime computing on top of Storm. It allows you to seamlessly intermix high throughput (millions of messages per second), stateful stream processing with low latency distributed querying. If you’re familiar with high level batch processing tools like Pig or Cascading, the concepts of Trident will be very familiar – Trident has joins, aggregations, grouping, functions, and filters. In addition to these, Trident adds primitives for doing stateful, incremental processing on top of any database or persistence store. Trident has consistent, exactly-once semantics, so it is easy to reason about Trident topologies.
Illustrative example
Let’s look at an illustrative example of Trident. This example will do two things:
- Compute streaming word count from an input stream of sentences
- Implement queries to get the sum of the counts for a list of words
For the purposes of illustration, this example will read an infinite stream of sentences from the following source:
java
FixedBatchSpout spout = new FixedBatchSpout(new Fields("sentence"), 3,
new Values("the cow jumped over the moon"),
new Values("the man went to the store and bought some candy"),
new Values("four score and seven years ago"),
new Values("how many apples can you eat"));
spout.setCycle(true);
This spout cycles through that set of sentences over and over to produce the sentence stream. Here’s the code to do the streaming word count part of the computation:
java
TridentTopology topology = new TridentTopology();
TridentState wordCounts =
topology.newStream("spout1", spout)
.each(new Fields("sentence"), new Split(), new Fields("word"))
.groupBy(new Fields("word"))
.persistentAggregate(new MemoryMapState.Factory(), new Count(), new Fields("count"))
.parallelismHint(6);
Let’s go through the code line by line. First a TridentTopology object is created, which exposes the interface for constructing Trident computations. TridentTopology has a method called newStream that creates a new stream of data in the topology reading from an input source. In this case, the input source is just the FixedBatchSpout defined from before. Input sources can also be queue brokers like Kestrel or Kafka. Trident keeps track of a small amount of state for each input source (metadata about what it has consumed) in Zookeeper, and the “spout1” string here specifies the node in Zookeeper where Trident should keep that metadata.
Trident processes the stream as small batches of tuples. For example, the incoming stream of sentences might be divided into batches like so:
Generally the size of those small batches will be on the order of thousands or millions of tuples, depending on your incoming throughput.
Trident provides a fully fledged batch processing API to process those small batches. The API is very similar to what you see in high level abstractions for Hadoop like Pig or Cascading: you can do group by’s, joins, aggregations, run functions, run filters, and so on. Of course, processing each small batch in isolation isn’t that interesting, so Trident provides functions for doing aggregations across batches and persistently storing those aggregations – whether in memory, in Memcached, in Cassandra, or some other store. Finally, Trident has first-class functions for querying sources of realtime state. That state could be updated by Trident (like in this example), or it could be an independent source of state.
Back to the example, the spout emits a stream containing one field called “sentence”. The next line of the topology definition applies the Split function to each tuple in the stream, taking the “sentence” field and splitting it into words. Each sentence tuple creates potentially many word tuples – for instance, the sentence “the cow jumped over the moon” creates six “word” tuples. Here’s the definition of Split:
java
public class Split extends BaseFunction {
public void execute(TridentTuple tuple, TridentCollector collector) {
String sentence = tuple.getString(0);
for(String word: sentence.split(" ")) {
collector.emit(new Values(word));
}
}
}
As you can see, it’s really simple. It simply grabs the sentence, splits it on whitespace, and emits a tuple for each word.
The rest of the topology computes word count and keeps the results persistently stored. First the stream is grouped by the “word” field. Then, each group is persistently aggregated using the Count aggregator. The persistentAggregate function knows how to store and update the results of the aggregation in a source of state. In this example, the word counts are kept in memory, but this can be trivially swapped to use Memcached, Cassandra, or any other persistent store. Swapping this topology to store counts in Memcached is as simple as replacing the persistentAggregate line with this (using trident-memcached), where the “serverLocations” is a list of host/ports for the Memcached cluster:
java
.persistentAggregate(MemcachedState.transactional(serverLocations), new Count(), new Fields("count"))
MemcachedState.transactional()
The values stored by persistentAggregate represents the aggregation of all batches ever emitted by the stream.
One of the cool things about Trident is that it has fully fault-tolerant, exactly-once processing semantics. This makes it easy to reason about your realtime processing. Trident persists state in a way so that if failures occur and retries are necessary, it won’t perform multiple updates to the database for the same source data.
The persistentAggregate method transforms a Stream into a TridentState object. In this case the TridentState object represents all the word counts. We will use this TridentState object to implement the distributed query portion of the computation.
The next part of the topology implements a low latency distributed query on the word counts. The query takes as input a whitespace separated list of words and return the sum of the counts for those words. These queries are executed just like normal RPC calls, except they are parallelized in the background. Here’s an example of how you might invoke one of these queries:
java
DRPCClient client = new DRPCClient("drpc.server.location", 3772);
System.out.println(client.execute("words", "cat dog the man");
// prints the JSON-encoded result, e.g.: "[[5078]]"
As you can see, it looks just like a regular remote procedure call (RPC), except it’s executing in parallel across a Storm cluster. The latency for small queries like this are typically around 10ms. More intense DRPC queries can take longer of course, although the latency largely depends on how many resources you have allocated for the computation.
The implementation of the distributed query portion of the topology looks like this:
java
topology.newDRPCStream("words")
.each(new Fields("args"), new Split(), new Fields("word"))
.groupBy(new Fields("word"))
.stateQuery(wordCounts, new Fields("word"), new MapGet(), new Fields("count"))
.each(new Fields("count"), new FilterNull())
.aggregate(new Fields("count"), new Sum(), new Fields("sum"));
The same TridentTopology object is used to create the DRPC stream, and the function is named “words”. The function name corresponds to the function name given in the first argument of execute when using a DRPCClient.
Each DRPC request is treated as its own little batch processing job that takes as input a single tuple representing the request. The tuple contains one field called “args” that contains the argument provided by the client. In this case, the argument is a whitespace separated list of words.
First, the Split function is used to split the arguments for the request into its constituent words. The stream is grouped by “word”, and the stateQuery operator is used to query the TridentState object that the first part of the topology generated. stateQuery takes in a source of state – in this case, the word counts computed by the other portion of the topology – and a function for querying that state. In this case, the MapGet function is invoked, which gets the count for each word. Since the DRPC stream is grouped the exact same way as the TridentState was (by the “word” field), each word query is routed to the exact partition of the TridentState object that manages updates for that word.
Next, words that didn’t have a count are filtered out via the FilterNull filter and the counts are summed using the Sum aggregator to get the result. Then, Trident automatically sends the result back to the waiting client.
Trident is intelligent about how it executes a topology to maximize performance. There’s two interesting things happening automatically in this topology:
- Operations that read from or write to state (like persistentAggregate and stateQuery) automatically batch operations to that state. So if there’s 20 updates that need to be made to the database for the current batch of processing, rather than do 20 read requests and 20 writes requests to the database, Trident will automatically batch up the reads and writes, doing only 1 read request and 1 write request (and in many cases, you can use caching in your State implementation to eliminate the read request). So you get the best of both words of convenience – being able to express your computation in terms of what should be done with each tuple – and performance.
- Trident aggregators are heavily optimized. Rather than transfer all tuples for a group to the same machine and then run the aggregator, Trident will do partial aggregations when possible before sending tuples over the network. For example, the Count aggregator computes the count on each partition, sends the partial count over the network, and then sums together all the partial counts to get the total count. This technique is similar to the use of combiners in MapReduce.
Let’s look at another example of Trident.
Reach
The next example is a pure DRPC topology that computes the reach of a URL on demand. Reach is the number of unique people exposed to a URL on Twitter. To compute reach, you need to fetch all the people who ever tweeted a URL, fetch all the followers of all those people, unique that set of followers, and that count that uniqued set. Computing reach is too intense for a single machine – it can require thousands of database calls and tens of millions of tuples. With Storm and Trident, you can parallelize the computation of each step across a cluster.
This topology will read from two sources of state. One database maps URLs to a list of people who tweeted that URL. The other database maps a person to a list of followers for that person. The topology definition looks like this:
```java TridentState urlToTweeters = topology.newStaticState(getUrlToTweetersState()); TridentState tweetersToFollowers = topology.newStaticState(getTweeterToFollowersState());
topology.newDRPCStream(“reach”) .stateQuery(urlToTweeters, new Fields(“args”), new MapGet(), new Fields(“tweeters”)) .each(new Fields(“tweeters”), new ExpandList(), new Fields(“tweeter”)) .shuffle() .stateQuery(tweetersToFollowers, new Fields(“tweeter”), new MapGet(), new Fields(“followers”)) .parallelismHint(200) .each(new Fields(“followers”), new ExpandList(), new Fields(“follower”)) .groupBy(new Fields(“follower”)) .aggregate(new One(), new Fields(“one”)) .parallelismHint(20) .aggregate(new Count(), new Fields(“reach”)); ```
The topology creates TridentState objects representing each external database using the newStaticState method. These can then be queried in the topology. Like all sources of state, queries to these databases will be automatically batched for maximum efficiency.
The topology definition is straightforward – it’s just a simple batch processing job. First, the urlToTweeters database is queried to get the list of people who tweeted the URL for this request. That returns a list, so the ExpandList function is invoked to create a tuple for each tweeter.
Next, the followers for each tweeter must be fetched. It’s important that this step be parallelized, so shuffle is invoked to evenly distribute the tweeters among all workers for the topology. Then, the followers database is queried to get the list of followers for each tweeter. You can see that this portion of the topology is given a large parallelism since this is the most intense portion of the computation.
Next, the set of followers is uniqued and counted. This is done in two steps. First a “group by” is done on the batch by “follower”, running the “One” aggregator on each group. The “One” aggregator simply emits a single tuple containing the number one for each group. Then, the ones are summed together to get the unique count of the followers set. Here’s the definition of the “One” aggregator:
```java
public class One implements CombinerAggregator
public Integer combine(Integer val1, Integer val2) { return 1; }
public Integer zero() {
return 1;
}
}
```
This is a “combiner aggregator”, which knows how to do partial aggregations before transferring tuples over the network to maximize efficiency. Sum is also defined as a combiner aggregator, so the global sum done at the end of the topology will be very efficient.
Let’s now look at Trident in more detail.
Fields and tuples
The Trident data model is the TridentTuple which is a named list of values. During a topology, tuples are incrementally built up through a sequence of operations. Operations generally take in a set of input fields and emit a set of “function fields”. The input fields are used to select a subset of the tuple as input to the operation, while the “function fields” name the fields the operation emits.
Consider this example. Suppose you have a stream called “stream” that contains the fields “x”, “y”, and “z”. To run a filter MyFilter that takes in “y” as input, you would say:
java
stream.each(new Fields("y"), new MyFilter())
Suppose the implementation of MyFilter is this:
java
public class MyFilter extends BaseFilter {
public boolean isKeep(TridentTuple tuple) {
return tuple.getInteger(0) < 10;
}
}
This will keep all tuples whose “y” field is less than 10. The TridentTuple given as input to MyFilter will only contain the “y” field. Note that Trident is able to project a subset of a tuple extremely efficiently when selecting the input fields: the projection is essentially free.
Let’s now look at how “function fields” work. Suppose you had this function:
java
public class AddAndMultiply extends BaseFunction {
public void execute(TridentTuple tuple, TridentCollector collector) {
int i1 = tuple.getInteger(0);
int i2 = tuple.getInteger(1);
collector.emit(new Values(i1 + i2, i1 * i2));
}
}
This function takes two numbers as input and emits two new values: the addition of the numbers and the multiplication of the numbers. Suppose you had a stream with the fields “x”, “y”, and “z”. You would use this function like this:
java
stream.each(new Fields("x", "y"), new AddAndMultiply(), new Fields("added", "multiplied"));
The output of functions is additive: the fields are added to the input tuple. So the output of this each call would contain tuples with the five fields “x”, “y”, “z”, “added”, and “multiplied”. “added” corresponds to the first value emitted by AddAndMultiply, while “multiplied” corresponds to the second value.
With aggregators, on the other hand, the function fields replace the input tuples. So if you had a stream containing the fields “val1” and “val2”, and you did this:
java
stream.aggregate(new Fields("val2"), new Sum(), new Fields("sum"))
The output stream would only contain a single tuple with a single field called “sum”, representing the sum of all “val2” fields in that batch.
With grouped streams, the output will contain the grouping fields followed by the fields emitted by the aggregator. For example:
java
stream.groupBy(new Fields("val1"))
.aggregate(new Fields("val2"), new Sum(), new Fields("sum"))
In this example, the output will contain the fields “val1” and “sum”.
State
A key problem to solve with realtime computation is how to manage state so that updates are idempotent in the face of failures and retries. It’s impossible to eliminate failures, so when a node dies or something else goes wrong, batches need to be retried. The question is – how do you do state updates (whether external databases or state internal to the topology) so that it’s like each message was only processed only once?
This is a tricky problem, and can be illustrated with the following example. Suppose that you’re doing a count aggregation of your stream and want to store the running count in a database. If you store only the count in the database and it’s time to apply a state update for a batch, there’s no way to know if you applied that state update before. The batch could have been attempted before, succeeded in updating the database, and then failed at a later step. Or the batch could have been attempted before and failed to update the database. You just don’t know.
Trident solves this problem by doing two things:
- Each batch is given a unique id called the “transaction id”. If a batch is retried it will have the exact same transaction id.
- State updates are ordered among batches. That is, the state updates for batch 3 won’t be applied until the state updates for batch 2 have succeeded.
With these two primitives, you can achieve exactly-once semantics with your state updates. Rather than store just the count in the database, what you can do instead is store the transaction id with the count in the database as an atomic value. Then, when updating the count, you can just compare the transaction id in the database with the transaction id for the current batch. If they’re the same, you skip the update – because of the strong ordering, you know for sure that the value in the database incorporates the current batch. If they’re different, you increment the count.
 This logic is wrapped by the State abstraction and done automatically. Nor is your State object required to implement the transaction id trick: if you don’t want to pay the cost of storing the transaction id in the database, you don’t have to. In that case the State will have at-least-once-processing semantics in the case of failures (which may be fine for your application). You can read more about how to implement a State and the various fault-tolerance tradeoffs possible in this doc.
A State is allowed to use whatever strategy it wants to store state. So it could store state in an external database or it could keep the state in-memory but backed by HDFS (like how HBase works). State’s are not required to hold onto state forever. For example, you could have an in-memory State implementation that only keeps the last X hours of data available and drops anything older. Take a look at the implementation of the Memcached integration for an example State implementation.
Execution of Trident topologies
Trident topologies compile down into as efficient of a Storm topology as possible. Tuples are only sent over the network when a repartitioning of the data is required, such as if you do a groupBy or a shuffle. So if you had this Trident topology:
It would compile into Storm spouts/bolts like this:
Conclusion
Trident makes realtime computation elegant. You’ve seen how high throughput stream processing, state manipulation, and low-latency querying can be seamlessly intermixed via Trident’s API. Trident lets you express your realtime computations in a natural way while still getting maximal performance.


To analyse the listed directors of UK companies to find out what proportion were male / female
The total size of the data-set was all companies registered with Companies House in the UK
We then narrowed this data-set to companies who were obliged to publish gender pay gap information.
This is a requirement for all companies with 250 or more employees
Some companies with fewer than 250 employess have voluntarily published this data, they have also been included
10,513 companies
For company directors, we have access to specific numbers eg 10 directors, 5 males and 5 females
For pay data (salaries and bonuses), we have representative data.
For example, pay is divided into 4 quartiles, (lower, lower-middle, upper-middle and upper).
Companies will declare how many males ad


A Study in Art
Articles
Reproductions
Reviews
Studies
Pen Drawings of Florence
by Herbert Railton
Update 1
Update 2


| HOSTS.EQUIV(5) | Linux Programmer's Manual | HOSTS.EQUIV(5) |
The file uses the following format:
The hostname is the name of a host which is logically equivalent to the local host. Users logged into that host are allowed to access like-named user accounts on the local host without supplying a password. The hostname may be (optionally) preceded by a plus (+) sign. If the plus sign is used alone, it allows any host to access your system. You can explicitly deny access to a host by preceding the hostname by a minus (-) sign. Users from that host must always supply additional credentials, including possibly a password. For security reasons you should always use the FQDN of the hostname and not the short hostname.
The username entry grants a specific user access to all user accounts (except root) without supplying a password. That means the user is NOT restricted to like-named accounts. The username may be (optionally) preceded by a plus (+) sign. You can also explicitly deny access to a specific user by preceding the username with a minus (-) sign. This says that the user is not trusted no matter what other entries for that host exist.
Netgroups can be specified by preceding the netgroup by an @ sign.
Be extremely careful when using the plus (+) sign. A simple typographical error could result in a standalone plus sign. A standalone plus sign is a wildcard character that means "any host"!
Modern systems use the Pluggable Authentication Modules library (PAM). With PAM a standalone plus sign is considered a wildcard character which means "any host" only when the word promiscuous is added to the auth component line in your PAM file for the particular service (e.g., rlogin).
Allow any user to log in from any host:
+
Allow any user from host with a matching local account to log in:
host
Note: the use of +host is never a valid syntax, including attempting to specify that any user from the host is allowed.
Allow any user from host to log in:
host +
Note: this is distinct from the previous example since it does not require a matching local account.
Allow user from host to log in as any non-root user:
host user
Allow all users with matching local accounts from host to log in except for baduser:
host -baduser host
Deny all users from host:
-host
Note: the use of -host -user is never a valid syntax, including attempting to specify that a particular user from the host is not trusted.
Allow all users with matching local accounts on all hosts in a netgroup:
+@netgroup
Disallow all users on all hosts in a netgroup:
-@netgroup
Allow all users in a netgroup to log in from host as any non-root user:
host +@netgroup
Allow all users with matching local accounts on all hosts in a netgroup except baduser:
+@netgroup -baduser +@netgroup
Note: the deny statements must always precede the allow statements because the file is processed sequentially until the first matching rule is found.
| 2015-07-23 | Linux |


--- layout: plain title: Events ---
I have started, organise, and help out with various events in Bournemouth.Here's a few of them.
Free hackdays for developers For learning, fun, and community
Learn more
Developer conference in Bournemouth Returning in August 2015


Total Raised
$15,000
For this demo the socket.IO server will update the Total Raised and Young Alumni Challenge every 15 seconds.
Parents Council Challenge - Dollar-for-dollar match up to $12,250 (8 am - 12 am)
Challenge complete!
Young Alumni Challenge - Gifts from 1000 alumni who've graduated in the last 10 years unlock $23,000 (All Day)
100


The World Wide Web Consortium is the main international standards organization for the World Wide Web. Founded in 1994 and currently led by Tim Berners-Lee, the consortium is made up of member organizations that maintain full-time staff working together in the development of standards for the World Wide Web.
Its mission is to lead the World Wide Web to its full potential by developing standards, protocols and guidelines that ensure its long-term growth. Using W3C-compliant XML and CSS coding also improves search engine optimization by allowing search engine robots to “crawl” through websites quicker and more efficiently.
HyperText Markup Language (HTML) is the set of markup symbols or codes inserted into a file intended for display on the Internet. The markup tells web browsers how to display a web page's words and images.
HTML was made so that people do not have to write programs to just show a button, this widget was made by a simple markup, styled with a cascading style sheet and you can generate a good page with just that.
If you take JavaScript to write everything on a page, it will be programmatically intensive will not run with JavaScript disabled and you will end up having more bugs than you could have asked.
So, for very complex web pages people go for JavaScript tools (like react.js) to manipulate the DOM else for simple or static web pages HTML holds the ground for efficiency and hence it is very important.
For example, we can create a paragraph by placing the enclosed text within a starting <p> and closing </p> tag.
Cascading Style Sheets is a style sheet language used for describing the presentation of a document written in a markup language such as HTML. CSS is a cornerstone technology of the World Wide Web, alongside HTML and JavaScript.
CSS helps you to keep the informational content of a document separate from the details of how to display it. The details of how to display the document are known as its style. You keep the style separate from the content so that you can:
Want to create a designation for paragraphs that should be in small caps? A CSS sample for that would be:
p.smallcaps { font-variant: small-caps; }


Football: Kane hopes 'winner' Mourinho can end Spurs trophy drought
LONDON: Harry Kane hopes "proven winner" Jose Mourinho can deliver the trophies that Tottenham crave after taking over as manager from Mauricio Pochettino.
The Portuguese, back in the game after 11 months out, led his new club to a 3-2 win at West Ham on Saturday (Nov 23) - their first Premier League away win since January.
Kane was a staunch supporter of Pochettino, crediting him with making him into one of the top strikers in the world, and visited the Argentine at his home after his dismissal.
"It's a week I've never really had in my career before," said the England captain.
"It was a big shock on Tuesday night for everyone, the players included, and then it was a quick turnaround.
"All of a sudden we've got a new manager, one of the best managers there's been in the game, so automatically you have to turn your head towards that and focus on the game."
Pochettino, who took Spurs to the Champions League final in June, ended his five-and-a-half year stint with no silverware.
Kane has expressed his desire to win trophies at Spurs and is hoping that Mourinho, a former boss of Chelsea and Manchester United, can help him achieve his goals.
"The gaffer's won at every club he's gone to - there's no hiding away from that," Kane said.
"He wants to win. He's a proven winner. I've made it clear that I'm at the stage of my career where I want to win trophies.
"I've made it clear I want to win them here and it's a big year for us."
Kane said Mourinho's reputation for winning silverware gave the players confidence.
"It's almost a fresh slate for everyone now to show the manager what they can do and hopefully the players can thrive on that," he said.
Midfielder Eric Dier said the players were lucky to be able to work under Mourinho, whom he called the "perfect" replacement for Pochettino.
"His record is unbelievable and he transmits that confidence. The way he speaks, you believe it, you feel it from him," Dier said.


CMPT 295 Unit – Microprocessor Design & Instruction Execution
Lecture 29 – Sequential Logic Circuits and Sequential Execution
1
Carnegie Mellon
Last Lecture
2
Combinational logic circuits *Made of many logic gates *Multi-functional combinational logic circuits such as ALU have control input lines to indicate which function to perform *Combinational logic circuits do not store (remember) values Sequential logic circuits *Made of combinational logic circuits, memory elements (e.g., clocked registers) and clock *Circuit that “remembers” values (state) and perform computations on these values
Today’s Menu
- Instruction Set Architecture (ISA)
-
Definition of ISA
- Instruction Set design
- Design principles
- Look at an example of an instruction set: MIPS
- Create our own
-
ISA evaluation
- Implementation of a microprocessor (CPU) based on an ISA
- Execution of machine instructions (datapath)
- Intro to logic design + Combinational logic + Sequential logic circuit
- Sequential execution of machine instructions
- Pipelined execution of machine instructions + Hazards 3
About the word register
- Warning: the word register can mean different things!
- In hardware, a register is a hardware component directly connected to the rest of the circuit by its input and output lines (wires) *Called hardware register or clocked register
- In machine-level programming, a register is one of the addressable words in the CPU, i.e., in the register file (e.g., %rdi, %rax, etc…) *Called program register 4
*Implemented using hardware/clocked registers
Memory elements and Clock signals
- Memory element #1 -> clocked registers a.k.a. hardware registers
- On the microprocessor
- A clocked register stores 1 bit (state)
- Synchronized by system-wide clock
clocked register
- System-wide clock
- A system-wide clock sends 0 1 0 1 0 1 0 1…
- Clock period: 1 full cycle duration:
- Clock frequency: 1/period
CLOCK
- How clocked registers work:
- Output current state
- Input next state
5
- Next state remembered only on rising edge of clock
rising edge of clock
How a clocked register function!
Function Table
Load D 0 1 1
Q(t + 1) -> next state
X 0 1
Q(t) -> current state 0 1
Load 1) 0
Load 1) 0 clocked reg.
clocked reg.
1) 0
6
D
1) Q(t) Q 3) Q(t)
Load 1) 1
1) 1
D
1) Q(t) Q 3) Q(t)
Load 1) 1
clocked reg.
1) 0
D
1) Q(t) Q 3) 0
clocked reg.
1) 1
D
Q
1) Q(t) 3) 1
Clock
Clock
Clock
Clock
2) When the clock ticks, i.e., when edge of clock rises
2) When the clock ticks, i.e., when edge of clock rises
2) When the clock ticks, i.e., when edge of clock rises
2) When the clock ticks, i.e., when edge of clock rises
Row 1 of Function Table
Row 1 of Function Table
Row 2 of Function Table
Row 3 of Function Table
D flip flop
Edge-triggered clock
Load
Timing Diagram
clocked reg.
If clock period, then clock frequency is
Clock Load
0
1
0
1
0
1
D 1
Q
Clock
0
D Q tpd for register
7
Function Table Load 0 1 1
D X 0 1
Q(t + 1) Q(t) 0 1
Memory elements #2 -> Random
access memories
-
Made of several clocked registers, i.e., store multiple words of data
- Random access (as opposed to sequential access)
-
Use an address to select which of the many memory words should be read or written
- Examples:
- RAM (see video)
- Register file -> register id used as address
*Program registers 8
*For example: x86-64 register file holds 16 registers
valA
Register File
srcA
Read ports valB srcB
A
Register file
valW
W dstW
Write port
B
- Stores multiple words
Clock
- Each word is the value of a program register
- %rax, %rsp, etc.
-
Register ID serves as address to specify which word to read or write
- Multiple ports
- Can read and/or write multiple words in one clock cycle *Each port has separate address and data input/output 9
Register file – how it works?
valA srcA
output: value x input: register ID 2
valB srcB
A
- Reading
2 x
- Combinational logic circuit – does not need clock
Register file B
- Output data generated based on input address only, after some propagation delay
Clock
2 x Register file
valW
W dstW
input: value y register ID 2
2 y
Rising clock
Register file
valW
W dstW
input: value x register ID 2
Clock
Clock
- Writing
-
Sequential logic circuit -> clocked registers 10
- Remembers only when clock “ticks” (rising edge of clock)
Put together:
- Combinational logic circuits “deal” with an instruction
- Memory elements hold results (state), i.e., “remember”
memory element (clocked registers)
Clock 11
Value can be used in next clock cycle
Value written in a previous clock cycle
input combinational output output logic circuit input current state
next state
Clock cycle
memory element (clocked registers)
output current state
Sequential execution
- Now, imagine we have designed and implemented a microprocessor (its datapath): Called sequential execution because at every clock cycle, a new machine instruction is executed! 12
From textbook:
input
combinational logic circuit
output input next state
clock
memory element (clocked registers)
output current state
Analysis of sequential execution
the time between two ticks of the clock
- Clock cycle required to execute 1 instruction must exceed tpd of combinational logic circuit + tpd of clocked register execute 1 instruction
memory element
…
(clocked registers)
Clock
13
execute 1 instruction
input
combinational logic circuit
Clock cycle
-> tpd + tpd is long clock cycle!
output input next state
memory element (clocked registers)
output current state
Analysis of sequential execution (cont’d)
input
combinational logic circuit
output input next state
memory element (clocked registers)
output current state
clock
- Since the clock cycle is a factor in determining how fast the microprocessor executes machine instructions (i.e., execution speed)
-
Then a microprocessor with a long clock cycle is a slow microprocessor 14
- as it takes a long time to execute machine instructions, i.e., to execute a program
Conclusion: sequential execution
-
Such microprocessor called single-cycle microprocessor
- Execute each instruction in 1 clock cycle -> CPI = 1
- CPI => clock cycles per instruction *Def: the average number of clock cycles per instruction for a program or program fragment *inverse of instructions per cycle *one aspect of a processor’s performance
- CPI of 1 is inefficient:
-
Within the same clock cycle, functional units (of datapath like ALU) cannot be used more than once *So we would need to duplicate them if they are needed more than once during the execution of an instruction 15
- Results in a long clock cycle and a low throughput *Def of throughput: Number of instructions executed per second
Example of a single-cycle microprocessor
(datapath)
16 https://ict.iitk.ac.in/wp-content/uploads/CS422-Computer-Architecture-ComputerOrganizationAndDesign5thEdition2014.pdf
Analysis:
input
combinational logic circuit
output input next state
memory element (clocked registers)
output current state
clock
- Latency (same as propagation delay):
- Def: Time required to execute a single instruction
- Example:
- (instruction) Throughput -> speed of microprocessor: 17
- Def: Number of instructions executed per second - GIPS
- Example:
Summary
- We put combinational logic circuits and sequential logic circuits together -> datapath of a microprocessor
- Various models of Microprocessor machine instruction execution:
18
- Model 1: Sequential execution of machine instructions *The microprocessor we have just constructed is a sequential execution of machine instructions type of microprocessor since it executes one machine instruction at a time and per clock cycle *Single-cycle microprocessor (CPI = 1)
- In general, how to analyze various models of microprocessor instruction
execution:
- Latency (a.k.a. propagation delay): Time required to execute a single instruction
- Throughput: Number of instructions executed per second
- Conclusion of analyzing sequential execution of machine instructions
- Because this model requires a long clock cycle Creates slow microprocessors with small throughput
Next Lecture
- Instruction Set Architecture (ISA)
-
Definition of ISA
- Instruction Set design
- Design principles
- Look at an example of an instruction set: MIPS
- Create our own
-
ISA evaluation
- Implementation of a microprocessor (CPU) based on an ISA
- Execution of machine instructions (datapath)
- Intro to logic design + Combinational logic + Sequential logic circuit
- Sequential execution of machine instructions
- Pipelined execution of machine instructions + Hazards 19
##


ID:
Username:
Display Name:
Home
|
Logout
Here you can update your city and state!
City:
State:
SAVE
CHANGES PROPOSED FOR ME:


Switch to user
Home
CAR REPAIR WEBSITE
ADMIN DASHBOARD
You are logged in as an admin. You can either update the mechanics database or post new issues and fixes.
Please Fill in This Form
First Name:
Last Name
Car Model
Subaru
Toyota
BMW
Mazda
Hyundai
Nissan
Mitsubishi
Jeep
Volkswagen
Mercedes
Porsche
Audi
Volvo
What issue did you face?
How did you resolve it?
POST
THANK YOU FOR SHARING
First Name:
Last Name:
Contact:
update


My name is Cory Chassagne and I make content. Follow me around the internet:
Twitter | YouTube | Instagram TechnoToast.com | SkipTo.me