The articles I read - 2: Nulticore
As the number of cores grow from two to 64 performance plummets by a factor of five. Additional processors nullify each other. The author called it the Nulticore Effect. Read the full article here.
http://www.embedded.com/design/mcus-processors-and-socs/4008183/The-Nulticore-effect
This article sites IEEE Spectrum’s article.
http://spectrum.ieee.org/computing/hardware/multicore-is-bad-news-for-supercomputers
In past there had many few attempts to solve such issues. Berkeley IRAM was one of the significant one.
Few advances in chip fabrication technology as well as design practices in recent past can fuel new good ideas. Here is one of my idea.
The diagram above shows the concept where multiple processors access a Unified memory Complex which provides boost in memory throughput. The memory shown in the middle can be a monolithic single chip or collection of separate unit depending upon technology limitations.
Each Processor directly talks to dedicated Cache. It also accesses a copy of common memory devoted to it. These copies are kept in sync using an crossbar interconnect, possibly using an asynchronous design techniques.
All processors should be able to read the memory individually giving Nx speedup. The writes are also can be done individually at Nx speed as long as they are done to different area of address map. The asynchronous sync machine will sync up all N copies of memories in background using faster backdoor channels.
Divide by 1.5 Counter
This is one of the favourite questions asked in interviews. One of the best answers I found was in Xilinx’s Xcell magazine by one of my favorite authors, Peter Alfke. Check out his article called “Unusual Dividers” on page 30.
http://www.xilinx.com/publications/archives/xcell/Xcell33.pdf
This blog post is devoted to him. He died yesterday. Peter’s greatest talent was not simply that he was an FPGA expert but that he could communicate very technical content in a very practical and concise way.
“He was very proud that he came from a long line of educators,” said Carter. “His ability to take complex ideas and communicate them very clearly was really quite remarkable, especially when you realize that English was his second language. He liked to share his wisdom and never did it in arrogant manner. He was a fabulous diplomat, very approachable, very welcoming…a true gentleman.”
At lunchtime at Xilinx, Peter always drew a crowd of admiring friends to his table and there was always room for more. It was not uncommon to find 10 or more people sitting at a table built for 4 listening to Peter’s advice and sharing stories about all things under the sun.
Alfke is survived by his wife, son and daughter and two grandchildren. He was 79.
Read EETimes article , blog entry and EETimes news article for more details.
The first known FIFO implemented in electronics was done by Peter Alfke in 1969 at Fairchild Semiconductors. More details
Here is link to his patent on FIFO.
First-in, first-out buffer system in an integrated circuit
The articles I read - 2: Moving data across asynchronous clock boundaries
What strategy best addresses a situation where parallel data must pass across a clock domain boundary? The traditional method is to generate a flag and to use a handshake sequence.
When the transmitter has parallel data ready for transfer,it creates a rising edge on the READY line, which in turn sets flag F telling the receiver that data is available. The receiver scans F continuously and, after finding it high, accepts the stable parallel data and then creates a rising edge of ACK, which sets flip-flop A. This resets F, which in turn resets A. This particular design makes no assumptions about any phase or frequency relationship between the transmit and receive clocks. Such generality dictates a design using a benign
controlled race condition between the two flip-flops. A reasonable loop delay can conveniently be inserted between F and the reset of A. In a less generic design, this delay might be implemented as one period of either the transmit or receive clock.
This traditional handshake requires both sides to poll the flag F. The transmitter must change parallel data only when F is low, and the receiver must accept data only when F is high. This requirement results in a safe but slow data transfer. However, speedier ways to transfer data across an asynchronous clock boundary exist.
Peter Alfke's article was originally published in Integrated System Design magazine in 2000. A pdf of this article is available here. An html version of original article is archived here.
Interview Question 15: Create a compact data structure
A tree based data structure of distribution of post offices in a county is shown above.
- How do you store this data structure efficiently in a memory?
- Create a hardware (algorithm based) to find out whether given post office exists. For example if input to design is PO21 the module should traverse the data structure and show whether it exists or not.
Interview Question 14: Continuous Memory Read Writes
This is a high performance design question. Create a block which is an event counter as shown below.
This module is implemented using a single port memory as it has large number (millions) of counters. Every clock a valid signal indicates an increment or decrement operation of a counter indicated by an address. This block also produces output of the selected counter after a fixed latency.
Essentially you need to design a “Read-Modify-Write” operation. Assume that the chosen memory requires 2 clocks to complete the write and 2 clocks to read the data. The command and address combination can happen in any sequence. For example you may receive increment/decrement command for the same address on 10 consecutive clock cycles.
