Combinational Logic

From View

Jump to: navigation, search

Contents

Description

Combinational logic describes many simple, yet important functions which exploit bit-level parallelism to achieve high throughput. Workloads dominated by combinational logic computations generally involve performing simple operations on very large amounts of data. For example, computing checksums or CRCs is critical to network processing and ensuring data archive integrity, and can be accelerated with combinatorial logic. Performing simple Boolean operations such as and, or and xor on large data sets is important for applications such as RAID, and falls into the combinational logic category. Population count, or finding the number of ‘1’s in a word, is also an important combinational logic function useful for data mining. In general, whenever there is bit-level parallelism to be found, the computation can be accelerated by using dedicated combinational logic resources.

Combinational logic is very simple compared to many of the larger scale dwarfs. However, the need for high throughput combinational logic is increasing, as evidenced by Intel’s recent announcement of future inclusion of a programmable CRC generator and popcount unit to the x86 instruction set. It is also fairly straightforward to add computational units to processing elements which accelerate combinational logic, so it is easier to understand how supporting combinational logic well would impact a processor architecture.

Uniprocessor Mapping

On many architectures, the difficultly of programming combinational logic algorithms is due to lack of support for bit-level operations or variable-word-size operations in the ISA or the programming language.

Parallel Mapping

On many applications that employ combinational logic, algorithms may be broken into data pipelines, where each processor executes part of the pipeline and then passes the data to the next processor.

Elaboration

Credits

Links

x86 Popcount and CRC instruction extensions paper

x86 Popcount and CRC instruction extensions

Original text by Bryan Catanzaro.

Personal tools