9 Emerging Hardware Technologies for IoT Data Processing
457
A (5)
B (11)
C (7)
D (3)
E (8)
0
1
0
0
1
1
0
1
0
0
0
1
1
1
0
1
1
1
1
0
:
:
:
:
:
Median
? ? ? ?
:
(1) original data
(2) compute majority
A (5)
B (11)
C (7)
D (3)
E (8)
0
1
0
0
1
1
0
1
0
0
0
1
1
1
0
1
1
1
1
0
:
:
:
:
:
Median
0 ? ? ?
:
A (5)
B (11)
C (7)
D (3)
E (8)
0
1
0
0
1
1
1
1
0
1
0
1
1
0
1
0
1
1
0
1
:
:
:
:
:
Median
0 1 1 1
:
(4) final result
A (5)
B (11)
C (7)
D (3)
E (8)
0
1
0
0
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
:
:
:
:
:
Median
0 ? ? ?
:
(3) propagate minorities
Fig. 9.20 Computing the median of five numbers using the bit-serial algorithm
algorithm computes majority (2) and propagate minorities (3). The majority vote
computation is a vertical process that results in a single bit computed for the selected
column. The minority propagation is a horizontal process that depends on the result
of the majority function from the previous step. During the horizontal process, the
minority bits of the selected column are identified and are used to replace all of the
bits on their right-hand side. Repeating steps (2) and (3) for all bit positions results
in computing the median of all five numbers (4).
9.5.4 Memristive k-Median Clustering
The key idea of MISC is to exploit the computational capabilities of the memristive
arrays to perform the necessary computation for bit-serial median filtering in the
memory cells. Therefore, MISC can reduce the latency, bandwidth, and energy
overheads associated with streaming data out of the memory arrays during the
clustering process. By eliminating the need for transferring data to/from memory
arrays, MISC unlocks the unexploited massive parallelism in bit-serial median
algorithm for data clustering.
9.5.4.1 The MISC Architecture
The MISC accelerator is designed as a memory module that consists of multiple
chips. Figure 9.21 shows the hierarchical organization of MISC with respect to the
CPU and main memory. Every MISC chip comprises a hierarchy of data arrays
interconnected with a reconfigurable reduction tree. The memory cells are capable
of storing data bits and computing the basic operations required for bit-serial median
filters. The on-chip interconnection network allows for retrieving or merging partial
results from the data arrays. The MISC module is connected to the processor via a
standard double-data rate memory interface [107]. This modular organization of the
proposed accelerator allows the user to selectively integrate MISC in those computer
systems that execute data clustering workloads. The MISC memory architecture
supports two operational modes: the storage mode to serve ordinary read and write
requests and the compute mode that is for in situ data clustering. For a given
457
A (5)
B (11)
C (7)
D (3)
E (8)
0
1
0
0
1
1
0
1
0
0
0
1
1
1
0
1
1
1
1
0
:
:
:
:
:
Median
? ? ? ?
:
(1) original data
(2) compute majority
A (5)
B (11)
C (7)
D (3)
E (8)
0
1
0
0
1
1
0
1
0
0
0
1
1
1
0
1
1
1
1
0
:
:
:
:
:
Median
0 ? ? ?
:
A (5)
B (11)
C (7)
D (3)
E (8)
0
1
0
0
1
1
1
1
0
1
0
1
1
0
1
0
1
1
0
1
:
:
:
:
:
Median
0 1 1 1
:
(4) final result
A (5)
B (11)
C (7)
D (3)
E (8)
0
1
0
0
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
:
:
:
:
:
Median
0 ? ? ?
:
(3) propagate minorities
Fig. 9.20 Computing the median of five numbers using the bit-serial algorithm
algorithm computes majority (2) and propagate minorities (3). The majority vote
computation is a vertical process that results in a single bit computed for the selected
column. The minority propagation is a horizontal process that depends on the result
of the majority function from the previous step. During the horizontal process, the
minority bits of the selected column are identified and are used to replace all of the
bits on their right-hand side. Repeating steps (2) and (3) for all bit positions results
in computing the median of all five numbers (4).
9.5.4 Memristive k-Median Clustering
The key idea of MISC is to exploit the computational capabilities of the memristive
arrays to perform the necessary computation for bit-serial median filtering in the
memory cells. Therefore, MISC can reduce the latency, bandwidth, and energy
overheads associated with streaming data out of the memory arrays during the
clustering process. By eliminating the need for transferring data to/from memory
arrays, MISC unlocks the unexploited massive parallelism in bit-serial median
algorithm for data clustering.
9.5.4.1 The MISC Architecture
The MISC accelerator is designed as a memory module that consists of multiple
chips. Figure 9.21 shows the hierarchical organization of MISC with respect to the
CPU and main memory. Every MISC chip comprises a hierarchy of data arrays
interconnected with a reconfigurable reduction tree. The memory cells are capable
of storing data bits and computing the basic operations required for bit-serial median
filters. The on-chip interconnection network allows for retrieving or merging partial
results from the data arrays. The MISC module is connected to the processor via a
standard double-data rate memory interface [107]. This modular organization of the
proposed accelerator allows the user to selectively integrate MISC in those computer
systems that execute data clustering workloads. The MISC memory architecture
supports two operational modes: the storage mode to serve ordinary read and write
requests and the compute mode that is for in situ data clustering. For a given