El. knyga: Network Processor Design: Issues and Practices

About the Editors		v
Preface		xv
Network Processors: New Horizons		1	(8)
Patrick Crowley
Mark A. Franklin
Haldun Hadimioglu
Peter Z. Onufryk
Architecture		3	(1)
Tools and Techniques		4	(1)
Applications		5	(2)
Conclusions		7	(2)
References		7	(2)
Supporting Mixed Real-Time Workloads in Multithreaded Processors with Segmented Instruction Caches		9	(24)
Patrick Crowley
Instruction Delivery in NP Data Processors		11	(2)
Fixed-Size Control Store		11	(1)
Using a Cache as a Fixed-Size Control Store		12	(1)
Segmented Instruction Cache		13	(4)
Segment Sizing Strategies		14	(1)
Implementation		14	(2)
Address Mapping		16	(1)
Enforcing Instruction Memory Bandwidth Limits		17	(1)
Experimental Evaluation		17	(12)
Benchmark Programs and Methodology		17	(1)
Segment Sizing		18	(4)
Sources of Conflict Misses		22	(1)
Profile-Driven Code Scheduling to Reduce Misses		23	(2)
Using Set-Associativity to Reduce Misses		25	(2)
Segment Sharing		27	(2)
Related Work		29	(1)
Conclusions and Future Work		30	(3)
References		30	(3)
Efficient Packet Classification with Digest Caches		33	(22)
Francis Chang
Wu-chang Feng
Wu-chi Feng
Kang Li
Related Work		34	(1)
Our Approach		35	(7)
The Case for an Approximate Algorithm		36	(1)
Dimensioning a Digest Cache		37	(1)
Theoretical Comparison		37	(2)
A Specific Example of a Digest Cache		39	(2)
Exact Classification with Digest Caches		41	(1)
Evaluation		42	(7)
Reference Cache Implementations		44	(2)
Results		46	(3)
Hardware Overhead		49	(2)
IXP Overhead		49	(1)
Future Designs		50	(1)
Conclusions		51	(4)
Acknowledgments		52	(1)
References		52	(3)
Towards a Flexible Network Processor Interface for RapidIO, Hypertransport, and PCI-Express		55	(26)
Christian Sauer
Matthias Gries
Kurt Keutzer
Jose Ignacio Gomez
Interface Fundamentals and Comparison		57	(2)
Functional Layers		57	(2)
System Environment		59	(1)
Common Tasks		59	(1)
Modeling the Interfaces		59	(9)
Click for Packet-Based Interfaces		61	(1)
PCI Express		62	(3)
RapidIO		65	(1)
Hypertransport		66	(2)
Architecture Evaluation		68	(9)
Micro-Architecture Model		69	(1)
Simplified Instruction Set with Timing		69	(1)
Mapping and Implementation Details		70	(1)
Profiling Procedure		71	(1)
Results		72	(4)
Discussion		76	(1)
Conclusions		77	(4)
Acknowledgments		78	(1)
References		78	(3)
A High-Speed, Multithreaded TCP Offload Engine for 10 Gb/s Ethernet		81	(18)
Yatin Hoskote
Sriram Vangal
Vasantha Erraguntla
Nitin Borkar
Requirements on TCP Offload Solution		83	(4)
Architecture of TOE Solution		87	(8)
Architecture Details		87	(5)
TCP-Aware Hardware Multithreading and Scheduling Logic		92	(3)
Performance Analysis		95	(2)
Conclusions		97	(2)
Acknowledgments		98	(1)
References		98	(1)
A Hardware Platform for Network Intrusion Detection and Prevention		99	(20)
Chris Clark
Wenke Lee
David Schimmel
Didier Contis
Mohamed Kone
Ashley Thomas
Design Rationales and Principles		100	(4)
Motivation for Hardware-Based NNIDS		100	(1)
Characterization of NIDS Components		101	(2)
Hardware Architecture Considerations		103	(1)
Prototype NNIDS on a Network Interface		104	(6)
Hardware Platform		104	(2)
Snort Hardware Implementation		106	(1)
Network Interface to Host		107	(2)
Pattern Matching on the FPGA Coprocessor		109	(1)
Reusable IXP Libraries		110	(1)
Evaluation and Results		110	(5)
Functional Verification		111	(1)
Micro-Benchmarks		111	(3)
System Benchmarks		114	(1)
Conclusions		115	(4)
References		116	(3)
Packet Processing on a SIMD Stream Processor		119	(26)
Jathin S. Rai
Yu-Kuen Lai
Gregory T. Byrd
Background: Stream Programs and Architectures		120	(2)
Stream Programming Model		120	(1)
Imagine Stream Architecture		121	(1)
AES Encryption		122	(9)
Design Methodology and Implementation Details		123	(2)
Experiments		125	(5)
AES Performance Summary		130	(1)
IPv4 Forwarding		131	(8)
Design Methodology and Implementation Details		132	(2)
Experiments		134	(4)
IPv4 Performance Summary		138	(1)
Related Work		139	(1)
Conclusions and Future Work		140	(5)
Acknowledgments		142	(1)
References		142	(3)
A Programming Environment for Packet-Processing Systems: Design Considerations		145	(28)
Harrick Vin
Jayaram Mudigonda
Jamie Jason
Erik J. Johnson
Roy Ju
Aaron Kunze
Ruiqi Lian
Problem Domain		147	(3)
Packet-Processing Applications		147	(1)
Network Processor and System Architectures		148	(1)
Solution Requirements		149	(1)
Shangri-La: A Programming Environment for Packet-Processing Systems		150	(2)
Design Details and Challenges		152	(16)
Baker: A Domain-Specific Programming Language		152	(6)
Profile-Guided, Automated Mapping Compiler		158	(6)
Runtime System		164	(4)
Conclusions		168	(5)
References		169	(4)
RNOS---A Middleware Platform for Low-Cost Packet-Processing Devices		173	(24)
Jonas Greutert
Lothar Thiele
Scenario		174	(1)
Analysis Model of RNOS		175	(12)
Application Model		176	(3)
Input Model---SLA, Flows, and Microflows		179	(2)
Resource Model		181	(1)
Calculus		182	(5)
Implementation Model of RNOS		187	(5)
Path-Threads		188	(1)
Scheduler		188	(1)
Implementation		189	(3)
Measurements and Comparison		192	(1)
Conclusions and Outlook		193	(4)
Acknowledgments		194	(1)
References		194	(3)
On the Feasibility of Using Network Processors for DNA Queries		197	(22)
Herbert Bos
Kaiming Huang
Architecture		198	(12)
Scoring and Aligning		199	(2)
Hardware Configuration		201	(2)
Software Architecture		203	(4)
Aho-Corasick		207	(2)
Nucleotide Encoding		209	(1)
Implementation Details		210	(1)
Results		211	(4)
Related Work		215	(1)
Conclusions		216	(3)
Acknowledgments		217	(1)
References		217	(2)
Pipeline Task Scheduling on Network Processors		219	(26)
Mark A. Franklin
Seema Datar
The Pipeline Task Assignment Problem		221	(4)
Notation and Assignment Constraints		221	(2)
Performance Metrics		223	(1)
Related Work		224	(1)
The Greedypipe Algorithm		225	(3)
Basic Idea		225	(1)
Overall Algorithm		226	(1)
Greedypipe Performance		227	(1)
Pipeline Design with Greedypipe		228	(4)
Number of Pipeline Stages		229	(1)
Sharing of Tasks Between Flows		230	(1)
Task Partitioning		230	(2)
A Network Processor Problem		232	(10)
Longest Prefix Matching (LPM)		233	(3)
AES Encryption---A Pipelined Implementation		236	(2)
Data Compression---A Pipelined Implementation		238	(1)
Greedypipe NP Example Design Results		239	(3)
Conclusions		242	(3)
Acknowledgments		243	(1)
References		243	(2)
A Framework for Design Space Exploration of Resource Efficient Network Processing on Multiprocessor SoCs		245	(34)
Matthias Grunewald
Jorg-Christian Niemann
Mario Porrmann
Ulrich Ruckert
Related Work		247	(2)
Modeling Packet-Processing Systems		249	(6)
Flow Processing Graph		249	(4)
SoC Architecture		253	(2)
Scheduling		255	(6)
Forwarding Flow Segments Between PEs		256	(1)
Processing Flow Segments in PEs		257	(2)
A Scheduling Example		259	(2)
Mapping the Application to the System		261	(3)
Estimating the Resource Consumption		264	(4)
A Design Space Exploration Example		268	(7)
Application and System Parameters		268	(3)
Results		271	(4)
Conclusions		275	(4)
Acknowledgments		275	(1)
References		276	(3)
Application Analysis and Resource Mapping for Heterogeneous Network Processor Architectures		279	(30)
Ramaswamy Ramaswamy
Ning Weng
Tilman Wolf
Related Work		282	(1)
Application Analysis		283	(4)
Static vs. Dynamic Analysis		284	(1)
Annotated Directed Acyclic Graphs		285	(1)
Application Parallelism and Dependencies		285	(2)
ADAG Reduction		287	(1)
ADAG Clustering Using Maximum Local Ratio Cut		287	(4)
Clustering Problem Statement		288	(1)
Ratio Cut		289	(1)
Maximum Local Ratio Cut		290	(1)
MLRC Complexity		291	(1)
ADAG Results		291	(11)
The PacketBench Tool		291	(3)
Applications		294	(1)
Basic Block Results		295	(1)
Clustering Results		296	(3)
Application ADAGs		299	(1)
Identification of Coprocessor Functions		299	(3)
Mapping Application DAGs to NP Architectures		302	(4)
Problem Statement		302	(1)
Mapping Algorithm		303	(1)
Mapping and Scheduling Results		304	(2)
Conclusions		306	(3)
References		306	(3)
Index		309

Mark A. Franklin received his B.A., B.S.E.E. and M.S.E.E. from Columbia University, and his Ph.D. in EE from Carnegie-Mellon University. He is currently at Washington University in St. Louis where he has a joint appointment in Electrical Engineering and Computer Science, and holds the Urbauer Chair in Engineering. He founded and is Director of the Computer and Communications Research Center and until recently was the Director of the Undergraduate Program in Computer Engineering. Dr. Franklin is engaged in research, teaching and consulting in the areas of computer and communications architectures, ASIC and embedded processor design, parallel and distributed systems, and systems performance evaluation. He is a Fellow of the IEEE, a member of the ACM, and has been an organizer and reviewer for numerous professional conferences including the HPCA8 Workshop on Network Processors (2002). He has been Chair of the IEEE TCCA (Technical Committee on Computer Architecture), and Vice-Chairman of the ACM SIGARCH (Special Interest Group on Computer Architecture). Patrick Crowley is an associate Professor in the Department of Computer Science & Engineering at Washington University in St. Louis, Missouri. His research interests are in computer and network systems architecture, with a current focus on the design of programmable embedded network systems and the invention of superior network monitoring and security techniques. He co-founded the ACM/IEEE Symposium on Architectures for Networking and Communications Systems, and co-edited the three-book series, Network Processor Design. He serves as Associate Editor of the IEEE/ACM Transactions on Networking. In 2007, Crowley was chosen to join the DARPA Computer Science Study Group. Haldun Hadimioglu received his BS and MS degrees in Electrical Engineering at Middle East Technical University, Ankara Turkey and his Ph.D. in Computer Science from Polytechnic University in New York. He is currently an Industry Associate Professor in the Computer Science Department and a member of the Computer Engineering faculty at the Polytechnic University. He worked as a research engineer at PETAS, Ankara Turkey (1980-1982). Dr. Hadimioglu's research and teaching interests include Computer Architecture, Parallel and Distributed Systems, Networking and VLSI Design. He was a guest editor of the special issue on "Advances in High Performance Memory Systems," IEEE Transactions on Computers (Nov 2001) and has reviewed papers for leading journals such as the IEEE Transactions on Computers. Hadimioglu is a member of the IEEE, the ACM, and Sigma Xi. He has been an organizer of various workshops including, the ISCA Memory Wall (2000), ISCA Memory Performance Issues (2002, 2001) and HPCA8 Workshop on Network Processors (2002). He received Dedicated Faculty and Outstanding Faculty awards from Polytechnic students in 1995 and 1993, respectively. Peter Z. Onufryk received his B.S.E.E. from Rutgers University, M.S.E.E. from Purdue University, and Ph.D. in Electrical and Computer Engineering from Rutgers University. He is currently a director in the Internetworking Products Division at Integrated Device Technology, Inc. where he is responsible for architecture definition and validation of communications products. Before joining IDT, Peter was a researcher for thirteen years at AT&T Labs - Research (formally AT&T Bell Labs) where he worked on communications systems and parallel computer architectures. These included a number of parallel, cache-coherent multiprocessor and dataflow based machines that were targeted towards high performance military systems. Other work there focused on packet telephony and early network processors. Onufryk is a member of the IEEE. He was an organizer and program committee member of the HPCA8 Workshop on Network Processors 2002. Peter was the architect of four communications processors as well as numerous ASICs, boards, and systems.