2.2. Network
The Network category represents embedded
processors in network devices like switches and
routers. The work done by these embedded processors
involves shortest path calculations, tree and table
lookups and data input/output. The algorithms used to
demonstrate the networking category are finding a
shortest path in a graph and creating and searching a
Patricia trie data structure. Some of the benchmarks in
the Security and Telecommunications category are also
relevant to the Network category: CRC32, sha, and
blowfish. However, they are separated for organization.
dijkstra: The Dijkstra benchmark constructs a large
graph in an adjacency matrix representation and then
calculates the shortest path between every pair of nodes
using repeated applications of Dijkstra’s algorithm.
Dijkstra’s algorithm is a well known solution to the
shortest path problem and completes in O(n
2
) time.
patricia: A Patricia trie is a data structure used in
place of full trees with very sparse leaf nodes.
Branches with only a single leaf are collapsed upwards
in the trie to reduce traversal time at the expense of
code complexity. Often, Patricia tries are used to
represent routing tables in network applications. The
input data for this benchmark is a list of IP traffic from
a highly active web server for a 2 hour period. The IP
numbers are disguised.
2.3. Security
Data Security is going to have increased importance
as the Internet continues to gain popularity in e-
commerce activities. Therefore, Security is given its
own category in MiBench. The Security category
includes several common algorithms for data
encryption, decryption and hashing. One algorithm,
rijndael, is the new Advanced Encryption Standard
(AES) [12]. The other representative security
algorithms are Blowfish [13], PGP [15] and SHA [14].
blowfish encrypt/decrypt: Blowfish is a symmetric
block cipher with a variable length key. It was
developed in 1993 by Bruce Schneider. Since its key
length can range from 32 to 448 bits, it is ideal for
domestic and exportable encryption. The input data
sets are a large and small ASCII text file of an article
found online.
sha: SHA is the secure hash algorithm that produces
a 160-bit message digest for a given input. It is often
used in the secure exchange of cryptographic keys and
for generating digital signatures. It is also used in the
well-known MD4 and MD5 hashing functions. The
input data sets are the same as the ones used by
blowfish.
rijndael encrypt/decrypt: Rijndael was selected as
the National Institute of Standards and Technologies
Advanced Encryption Standard (AES). It is a block
cipher with the option of 128-, 192-, and 256-bit keys
and blocks. The input data sets are the same as the ones
used by blowfish.
pgp sign/verify: Pretty Good Privacy (PGP) is a
public key encryption algorithm developed by Phil
Zimmerman. It allows you to communicate securely
with people you’ve never met using digital signatures
and the RSA public key cryptosystem. The input data
for both the large and small tests is a small text file.
This is because PGP is usually only used to securely
exchange a key for a block cipher which can then
encrypt/decrypt data at a much faster rate.
2.4. Consumer Devices
The Consumer Devices benchmarks are intended to
represent the many consumer devices that have grown
in popularity during recent years like scanners, digital
cameras and Personal Digital Assistants (PDAs). The
Table 1: MiBench Benchmarks
Auto./Industrial Consumer Office Network Security Telecomm.
basicmath jpeg ghostscript dijkstra blowfish enc. CRC32
bitcount lame ispell patricia blowfish dec. FFT
qsort mad rsynth (CRC32) pgp sign IFFT
susan (edges) tiff2bw sphinx (sha) pgp verify ADPCM enc.
susan (corners) tiff2rgba stringsearch (blowfish) rijndael enc. ADPCM dec.
susan (smoothing) tiffdither rijndael dec. GSM enc.
tiffmedian sha GSM dec.
typeset