Transcript 01471r0P802-15_TG2-Complexity-Comparison-of-TG2

October, 2001
doc.: IEEE 802.15-01/471r0
Project: IEEE P802.15 Working Group for Wireless Personal Area Networks (WPANs)
Submission Title: Complexity Comparison of TG2 AFH Mechanisms
Date Submitted: October 8, 2001
Source: (1) HK Chen, YC Maa, and KC Chen (2) Anuj Batra, Kofi Anim-Appiah, and Jin-Meng Ho
Company: (1) Integrated Programmable Communications, Inc. (2) Texas Instruments, Inc.
Address: (1)Taiwan Laboratories Address: P.O. Box 24-226, Hsinchu, Taiwan 300
(2) 12500 TI Boulevard, Dallas, TX 75243
TEL(1) +886 3 516 5106, FAX: +886 3 516 5108, E-Mail: {hkchen, ycmaa, kc}@inprocomm.com
(2) +1 214 480 4220, FAX: 972 761 6966, E-Mail: {batra, kofi, jinmengho}@ti.com
Re: []
Abstract: This presentation shows the complexity estimations for AFH mechanisms
Purpose: Submission to Task Group 2 to resolve the complexity consideration.
Notice: This document has been prepared to assist the IEEE P802.15. It is offered as a basis for
discussion and is not binding on the contributing individual(s) or organization(s). The material in this
document is subject to change in form and content after further study. The contributor(s) reserve(s) the right
to add, amend or withdraw material contained herein.
Release: The contributor acknowledges and accepts that this contribution becomes the property of IEEE
and may be made publicly available by P802.15.
Submission
Slide 1
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Complexity Comparison of TG2 AFH
Mechanisms
HK Chen, YC Maa, and KC Chen
Integrated Programmable Communications
Anuj Batra, Kofi Anim-Appiah, and Jin-Meng Ho
Texas Instruments
Submission
Slide 2
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Scope of Complexity Estimation
What IS NOT in this complexity estimation
 Channel classification algorithm
 Pseudo-random number generator
What IS in this complexity estimation
 Major components for adaptive hopping sequence
generation
• Mapping function
• Partition sequence generation
 Comparison of hardware/software/mixed
implementations.
Submission
Slide 3
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Hardware Implementation Assumption
 Unit of gate count: NAND gate.
 Use one hardware block for multiple occurrences of
the same operation.
 Ex: there may be several mod operations, but only one
div/mod hardware is needed.
 Variable storage/mapping table: 4 gates per bits.
 Division/Mod operation
 A=B*Q+R, Q=floor(A/B), R = A mod B
 It can be implement in hardware by long-division :
• Multiple clock implementation, shift-in one bit of operand “A” at each
clock.
• Require WA clocks to finish one operation, where WA is the width
(number of bits) of operand A.
• Gate count required is in proportional to WB .
Submission
Slide 4
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Hardware Implementation:
Mode L Mapping
Hardware blocks:
 Adder
• 12-bits
• Gate count = 0.1K
 Mod
• WB=7
• Gate count = 1K
 Mapping table
• 79*7 bits
• Gate count = 2K
Total gate count = 3.1K
Submission
Slide 5
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Hardware Implementation:
Mode H Mapping
Hardware blocks:
 Adder
• 12-bits
• Gate count = 0.1K
 Mod
• WB=7
• Gate count = 1K
 Mapping table
• 79*7 bits
• Gate count = 2K
 Misc
• 0.2 K
Total gate count = 3.3K
Submission
Slide 6
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Hardware Implementation:
Mode H Partition Sequence
Hardware blocks:
 Multiplier: 8bit x 8 bit, parallel multiplier
• Gate count = 0.5K
 Division/Mod
• WB=8
• Gate count = 1K
 Add/Sub
• Gate count = 0.1K
 Variable storage and procedure control
• Gate count = 1K
 Misc
• Gate count = 0.2K
Total gate count = 2.8 K
Submission
Slide 7
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Hardware Implementation: Mode H
The complexity of mode H is the sum of
mapping and partition sequence
Direct summation of the two gate count
numbers: 3.3K + 2.8K = 6.1K
Note that the mod/division block can be
further shared
• Gate count can be reduced to 5.1K
Submission
Slide 8
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Software Implementation Assumption(1)
Division/Mod operation
 A=B*Q+R, Q=floor(A/B), R = A mod B
 It can be implement in software by long-division :
• Each iteration requires four operations:
– One conditional subtraction
– Two shift operations
– One loop instruction
• Number of iterations required is equal to the width (
number of bits) of A, WA.
• The total instruction cycles required is roughly 4* WA.
Submission
Slide 9
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Software Implementation Assumption(2)
Multiplication
 Many processors have special instruction for
multiplication (C=A*B).
 If not, it can be implement in software
• Each iteration requires 3 operations:
– One conditional addition
– One shift operation
– One loop instruction
• Number of iterations required is equal to min{WA ,WB}-1
• The total instruction cycles required is roughly
3*(min{WA ,WB}-1)
Submission
Slide 10
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Software Implementation:
Mode L Mapping
Instructions
 Mod operation X 1:
• Assume 12-bits pseudo-random signal, thus 12-bit mod
operation
• 48 instruction cycles
 Misc instructions
• Add/if-then-else/table-lookup/load-store variables
• 10 instruction cycles
 Totally 58 instruction cycles
Load
 58/625us = 0.0928 MIPS
Submission
Slide 11
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Software Implementation:
Mode H Mapping
Instructions
 Mod operation X 1:
• Assume 12-bits pseudo-random signal, thus 12-bit mod
operation
• 48 instruction cycles
 Misc instructions
• Add/if-then-else/table-lookup/load-store variables
• 20 instruction cycles
 Totally 68 instruction cycles
 Load
• 68/625us = 0.1088 MIPS
Submission
Slide 12
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Software Implementation:
Mode H Partition Sequence-SCO (1)
 For the first MAU (master-slave pair)
 Distribution unit: Variables initial calculations
• Div/Mod operations X 6
– 27bits x 1, 9bits x 1, 8bits x 1, 7bits x 3
– 4*(27+9+8+7*3)= 260 instruction cycles
• Multiplications X 2
– 3bits X 2
– 12 instructions cycles
• Misc instructions
– 20 instruction cycles
 Arrangement unit:
• if-then-else/table-lookup
– 10 instruction cycles
 Totally 302 instruction cycles
Submission
Slide 13
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Software Implementation:
Mode H Partition Sequence-SCO (2)
 For the remaining MAUs within one superframe
 Distribution unit:
• Variables update
• 30 instructions cycles
 Arrangement unit:
• if-then-else/table-lookup
• 10 instruction cycles
 Totally 40 instruction cycles
 For MAUs after one superframe




Submission
The partition sequence is periodic with superframe
The maximum length of superframe is 3*79 MAUs
Require 237 bits (about 30 bytes) to store one period
Table-lookup/index update: 10 instructions
Slide 14
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Software Implementation: Mode H
The complexity of mode H is the sum of
mapping and partition sequence
 Note that partition sequence is not calculated
every slot, but every MAU (two slots)
 For the first MAU:
• 0.1088MIPS + 302/(625us*2) = 0.3504 MIPS
 For the remaining MAUs within one superframe
• 0.1088MIPS + 40/(625us*2) = 0.1408 MIPS
 After one superframe
• 0.1088MIPS + 10/(625us*2) = 0.1168 MIPS
 For comparison, the number for mode L is
reproduced here : 0.0928 MIPS
Submission
Slide 15
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Comparison to some Bluetooth
mechanisms
 Some Bluetooth mechanisms also utilize sort of
frame/superframe structure
 SCO, sniff mode, park mode
 They requires some mod/division operations at
initialization.
 SCO as an example
• CLK27-1 mod Tsco = Dsco (Initialization 1)
• 27bits mod operation
• requires 108 instruction cycles
The utilization of mod operation and having
higher computation burden at initialization are
common in Bluetooth.
Submission
Slide 16
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Mixed Hardware/Software
Implementations
Implementations is generally somewhere
between the two extents of full hardware and
full software implementations.
One possibility:
 It is easily seen that the major software
computation burden comes from the mod/division
operation.
 One mod/division block takes about 1K gates.
 The remaining software computation power would
be less than 0.1MIPS.
• Mode H: 1K gates in hardware + 0.07 MIPS in software
• Mode L: 1K gates in hardware + 0.02 MIPS in software
Submission
Slide 17
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Reference Numbers for
Bluetooth Complexity
The hardware implementation of
Bluetooth baseband is about 30K ~ 50K
gates (not including digital modem
function)
The computation power required for
LMP, L2CAP, and HCI is about 10 ~ 20
MIPs, while typical processors can
easily provide up to 40 MIPs.
Submission
Slide 18
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Conclusions (1)
Complexity comparisons of AFH
mechanisms in hardware, software and
mixed implementations are presented.
The gate count of full hardware
implementation is in the reasonable
range.
The computation burden of mode H
software implementation is quite low
with today’s popular processors.
 The low computation burden is mainly because that
AFH is operated once per slot, which is a long period.
Submission
Slide 19
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.
October, 2001
doc.: IEEE 802.15-01/471r0
Conclusions (2)
Some mixed hardware/software
implementation can have both a smaller
gate count and require extremely low
computation power.
AFH actually only contributes a very small
fraction to the complexity required for the
whole system. Thus we should consider
for best performance rather than
complexity reduction.
Submission
Slide 20
Integrated Programmable Communications, Inc. and Texas Instruments, Inc.