This document details the design and implementation of SIMD-like bit manipulation operations for the GPT-2 BASIC project, allowing us to process multiple values in parallel within standard 32-bit integers.
The SIMD-like software surface is implemented in src/simd_ops.bas and wired
into src/matrix_ops.bas. The assembly/fallback fixed-point support is in
src/asm_optimizations.bas, and the current production Q20.12 fixed-point path
is in src/real_gpt.bas. The closure probe
scripts/verify_aspirational_software.py records this status in
qemu/evidence/aspirational_software_closure.md; ICC reports
gpt2-basic-aspirational-software as ready with score 100.
CPU-specific physical calibration remains deferred with physical board timing. For now, emulator timing is the accepted runtime evidence basis.
The 486 processor lacks dedicated SIMD instructions that are common in modern CPUs. However, we can emulate SIMD-like behavior by packing multiple smaller values into a single 32-bit integer and operating on them simultaneously through bit manipulation. This "poor man's SIMD" approach can significantly accelerate certain operations, especially in matrix calculations which form the core of transformer models.
- Performance Improvement: Achieve 1.5-2x speedup for matrix operations
- Memory Efficiency: Reduce memory footprint by storing multiple values in a single integer
- Precision Options: Support multiple precision levels (4-bit, 8-bit, 16-bit)
- Flexibility: Allow dynamic selection of precision based on computational requirements
- Compatibility: Ensure operation on all 486-era hardware variants
┌────────────┬────────────┬────────────┬────────────┐
│ Value 4 │ Value 3 │ Value 2 │ Value 1 │
│ (8 bits) │ (8 bits) │ (8 bits) │ (8 bits) │
└────────────┴────────────┴────────────┴────────────┘
Bits 31-24 Bits 23-16 Bits 15-8 Bits 7-0
┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Val 8 │ Val 7 │ Val 6 │ Val 5 │ Val 4 │ Val 3 │ Val 2 │ Val 1 │
│(4 bits)│(4 bits)│(4 bits)│(4 bits)│(4 bits)│(4 bits)│(4 bits)│(4 bits)│
└────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘
31-28 27-24 23-20 19-16 15-12 11-8 7-4 3-0
┌────────────────────┬────────────────────┐
│ Value 2 │ Value 1 │
│ (16 bits) │ (16 bits) │
└────────────────────┴────────────────────┘
Bits 31-16 Bits 15-0
' Pack 4 8-bit values into a single 32-bit integer
FUNCTION Pack_8bit(v1 AS BYTE, v2 AS BYTE, v3 AS BYTE, v4 AS BYTE) AS LONG
FUNCTION = ((CLNG(v1) AND &HFF)) OR _
((CLNG(v2) AND &HFF) << 8) OR _
((CLNG(v3) AND &HFF) << 16) OR _
((CLNG(v4) AND &HFF) << 24)
END FUNCTION
' Pack 8 4-bit values into a single 32-bit integer
FUNCTION Pack_4bit(v1 AS BYTE, v2 AS BYTE, v3 AS BYTE, v4 AS BYTE, _
v5 AS BYTE, v6 AS BYTE, v7 AS BYTE, v8 AS BYTE) AS LONG
FUNCTION = ((CLNG(v1) AND &HF)) OR _
((CLNG(v2) AND &HF) << 4) OR _
((CLNG(v3) AND &HF) << 8) OR _
((CLNG(v4) AND &HF) << 12) OR _
((CLNG(v5) AND &HF) << 16) OR _
((CLNG(v6) AND &HF) << 20) OR _
((CLNG(v7) AND &HF) << 24) OR _
((CLNG(v8) AND &HF) << 28)
END FUNCTION
' Pack 2 16-bit values into a single 32-bit integer
FUNCTION Pack_16bit(v1 AS INTEGER, v2 AS INTEGER) AS LONG
FUNCTION = ((CLNG(v1) AND &HFFFF)) OR _
((CLNG(v2) AND &HFFFF) << 16)
END FUNCTION' Unpack 4 8-bit values from a single 32-bit integer
SUB Unpack_8bit(packed AS LONG, BYREF v1 AS BYTE, BYREF v2 AS BYTE, BYREF v3 AS BYTE, BYREF v4 AS BYTE)
v1 = packed AND &HFF
v2 = (packed >> 8) AND &HFF
v3 = (packed >> 16) AND &HFF
v4 = (packed >> 24) AND &HFF
END SUB
' Unpack 8 4-bit values from a single 32-bit integer
SUB Unpack_4bit(packed AS LONG, BYREF v1 AS BYTE, BYREF v2 AS BYTE, BYREF v3 AS BYTE, BYREF v4 AS BYTE, _
BYREF v5 AS BYTE, BYREF v6 AS BYTE, BYREF v7 AS BYTE, BYREF v8 AS BYTE)
v1 = packed AND &HF
v2 = (packed >> 4) AND &HF
v3 = (packed >> 8) AND &HF
v4 = (packed >> 12) AND &HF
v5 = (packed >> 16) AND &HF
v6 = (packed >> 20) AND &HF
v7 = (packed >> 24) AND &HF
v8 = (packed >> 28) AND &HF
END SUB
' Unpack 2 16-bit values from a single 32-bit integer
SUB Unpack_16bit(packed AS LONG, BYREF v1 AS INTEGER, BYREF v2 AS INTEGER)
v1 = packed AND &HFFFF
v2 = (packed >> 16) AND &HFFFF
END SUB' SIMD-like addition for 4 packed 8-bit values
FUNCTION SIMD_Add_8bit(a AS LONG, b AS LONG) AS LONG
DIM result AS LONG = a + b
DIM overflow_mask AS LONG = &H01010100 ' Bits that would carry between elements
' Handle potential overflow between elements by clearing carry bits
result = (result AND (NOT overflow_mask)) OR _
((a AND b AND overflow_mask))
FUNCTION = result
END FUNCTION
' SIMD-like subtraction for 4 packed 8-bit values
FUNCTION SIMD_Subtract_8bit(a AS LONG, b AS LONG) AS LONG
DIM result AS LONG
DIM underflow_mask AS LONG = &H01010100 ' Bits that would borrow between elements
' Set all potential borrow bits to 1 to prevent borrowing between elements
result = (a OR underflow_mask) - (b AND (NOT underflow_mask))
' Clear the borrow bits
result = result AND (NOT underflow_mask)
FUNCTION = result
END FUNCTION
' SIMD-like multiplication for 4 packed 8-bit values (low 8 bits of each product)
FUNCTION SIMD_Multiply_8bit(a AS LONG, b AS LONG) AS LONG
DIM a1 AS BYTE, a2 AS BYTE, a3 AS BYTE, a4 AS BYTE
DIM b1 AS BYTE, b2 AS BYTE, b3 AS BYTE, b4 AS BYTE
DIM result1 AS BYTE, result2 AS BYTE, result3 AS BYTE, result4 AS BYTE
' Unpack values
Unpack_8bit(a, a1, a2, a3, a4)
Unpack_8bit(b, b1, b2, b3, b4)
' Perform multiplications
result1 = (a1 * b1) AND &HFF
result2 = (a2 * b2) AND &HFF
result3 = (a3 * b3) AND &HFF
result4 = (a4 * b4) AND &HFF
' Repack results
FUNCTION = Pack_8bit(result1, result2, result3, result4)
END FUNCTION' SIMD-like addition for 8 packed 4-bit values
FUNCTION SIMD_Add_4bit(a AS LONG, b AS LONG) AS LONG
DIM result AS LONG = a + b
DIM overflow_mask AS LONG = &H11111110 ' Bits that would carry between elements
' Handle potential overflow between elements
result = (result AND (NOT overflow_mask)) OR _
((a AND b AND overflow_mask))
FUNCTION = result
END FUNCTION
' SIMD-like subtraction for 8 packed 4-bit values
FUNCTION SIMD_Subtract_4bit(a AS LONG, b AS LONG) AS LONG
DIM result AS LONG
DIM underflow_mask AS LONG = &H11111110 ' Bits that would borrow between elements
' Set all potential borrow bits to 1 to prevent borrowing between elements
result = (a OR underflow_mask) - (b AND (NOT underflow_mask))
' Clear the borrow bits
result = result AND (NOT underflow_mask)
FUNCTION = result
END FUNCTION' SIMD-like addition for 2 packed 16-bit values
FUNCTION SIMD_Add_16bit(a AS LONG, b AS LONG) AS LONG
DIM result AS LONG = a + b
DIM overflow_mask AS LONG = &H00010000 ' Bit that would carry between elements
' Handle potential overflow between elements
result = (result AND (NOT overflow_mask)) OR _
((a AND b AND overflow_mask))
FUNCTION = result
END FUNCTION
' SIMD-like subtraction for 2 packed 16-bit values
FUNCTION SIMD_Subtract_16bit(a AS LONG, b AS LONG) AS LONG
DIM result AS LONG
DIM underflow_mask AS LONG = &H00010000 ' Bit that would borrow between elements
' Set all potential borrow bits to 1 to prevent borrowing between elements
result = (a OR underflow_mask) - (b AND (NOT underflow_mask))
' Clear the borrow bits
result = result AND (NOT underflow_mask)
FUNCTION = result
END FUNCTION
' SIMD-like multiplication for 2 packed 16-bit values (low 16 bits of each product)
FUNCTION SIMD_Multiply_16bit(a AS LONG, b AS LONG) AS LONG
DIM a1 AS INTEGER, a2 AS INTEGER
DIM b1 AS INTEGER, b2 AS INTEGER
DIM result1 AS INTEGER, result2 AS INTEGER
' Unpack values
Unpack_16bit(a, a1, a2)
Unpack_16bit(b, b1, b2)
' Perform multiplications
result1 = (a1 * b1) AND &HFFFF
result2 = (a2 * b2) AND &HFFFF
' Repack results
FUNCTION = Pack_16bit(result1, result2)
END FUNCTION' Matrix multiplication using SIMD-like 8-bit operations
SUB MatrixMultiplySIMD_8bit(A AS Matrix, B AS Matrix, C AS Matrix)
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER, l AS INTEGER
DIM a_packed AS LONG, b_packed AS LONG, product AS LONG, sum AS LONG
DIM a_val(1 TO 4) AS BYTE, b_val(1 TO 4) AS BYTE
DIM result_val(1 TO 4) AS INTEGER
' Loop through rows of A
FOR i = 0 TO A.rows - 1
' Loop through columns of B
FOR j = 0 TO B.cols - 1
' Initialize accumulator
result_val(1) = 0
result_val(2) = 0
result_val(3) = 0
result_val(4) = 0
' Process 4 elements at a time
FOR k = 0 TO A.cols - 4 STEP 4
' Pack A row values
a_packed = Pack_8bit(A.data(i, k), A.data(i, k+1), A.data(i, k+2), A.data(i, k+3))
' Pack B column values
b_packed = Pack_8bit(B.data(k, j), B.data(k+1, j), B.data(k+2, j), B.data(k+3, j))
' Multiply packed values
product = SIMD_Multiply_8bit(a_packed, b_packed)
' Unpack and accumulate
Unpack_8bit(product, a_val(1), a_val(2), a_val(3), a_val(4))
result_val(1) = result_val(1) + a_val(1)
result_val(2) = result_val(2) + a_val(2)
result_val(3) = result_val(3) + a_val(3)
result_val(4) = result_val(4) + a_val(4)
NEXT k
' Handle any remaining elements
FOR l = k TO A.cols - 1
result_val(1) = result_val(1) + A.data(i, l) * B.data(l, j)
NEXT l
' Store the result
C.data(i, j) = result_val(1) + result_val(2) + result_val(3) + result_val(4)
NEXT j
NEXT i
END SUB' Matrix addition using SIMD-like 8-bit operations
SUB MatrixAddSIMD_8bit(A AS Matrix, B AS Matrix, C AS Matrix)
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER
DIM a_packed AS LONG, b_packed AS LONG, sum_packed AS LONG
DIM a_vals(1 TO 4) AS BYTE, b_vals(1 TO 4) AS BYTE, sum_vals(1 TO 4) AS BYTE
' Check dimensions
IF A.rows <> B.rows OR A.cols <> B.cols THEN
PRINT "Error: Matrix dimensions do not match for addition"
EXIT SUB
END IF
' Initialize result matrix
InitMatrix(C, A.rows, A.cols)
' Process 4 elements at a time
FOR i = 0 TO A.rows - 1
FOR j = 0 TO A.cols - 4 STEP 4
' Pack values from matrices A and B
a_packed = Pack_8bit(A.data(i, j), A.data(i, j+1), A.data(i, j+2), A.data(i, j+3))
b_packed = Pack_8bit(B.data(i, j), B.data(i, j+1), B.data(i, j+2), B.data(i, j+3))
' Add packed values
sum_packed = SIMD_Add_8bit(a_packed, b_packed)
' Unpack and store results
Unpack_8bit(sum_packed, sum_vals(1), sum_vals(2), sum_vals(3), sum_vals(4))
C.data(i, j) = sum_vals(1)
C.data(i, j+1) = sum_vals(2)
C.data(i, j+2) = sum_vals(3)
C.data(i, j+3) = sum_vals(4)
NEXT j
' Handle any remaining elements
FOR k = j TO A.cols - 1
C.data(i, k) = A.data(i, k) + B.data(i, k)
NEXT k
NEXT i
END SUBThe system will include functions to dynamically select the appropriate precision level based on the computational needs and hardware capabilities:
' Enumeration for precision levels
ENUM PrecisionLevel
PRECISION_4BIT = 1 ' Lowest precision, 8 values per 32-bit integer
PRECISION_8BIT = 2 ' Medium precision, 4 values per 32-bit integer
PRECISION_16BIT = 3 ' Higher precision, 2 values per 32-bit integer
PRECISION_32BIT = 4 ' Full precision, 1 value per 32-bit integer
END ENUM
' Determine the optimal precision level for a matrix operation
FUNCTION DetermineOptimalPrecision(rows AS INTEGER, cols AS INTEGER, operation_type AS INTEGER) AS PrecisionLevel
DIM matrix_size AS LONG = rows * cols
' Small matrices use higher precision
IF matrix_size < 256 THEN
RETURN PRECISION_32BIT
END IF
' Very large matrices use lowest precision
IF matrix_size > 4096 THEN
RETURN PRECISION_4BIT
END IF
' For attention operations, use lower precision
IF operation_type = OPERATION_ATTENTION AND matrix_size > 1024 THEN
RETURN PRECISION_4BIT
END IF
' Default to 8-bit precision
RETURN PRECISION_8BIT
END FUNCTION
' Matrix multiplication with adaptive precision
SUB MatrixMultiplyAdaptive(A AS Matrix, B AS Matrix, C AS Matrix, operation_type AS INTEGER)
DIM precision AS PrecisionLevel
' Determine optimal precision
precision = DetermineOptimalPrecision(A.rows, B.cols, operation_type)
' Call appropriate implementation based on precision
SELECT CASE precision
CASE PRECISION_4BIT:
MatrixMultiplySIMD_4bit(A, B, C)
CASE PRECISION_8BIT:
MatrixMultiplySIMD_8bit(A, B, C)
CASE PRECISION_16BIT:
MatrixMultiplySIMD_16bit(A, B, C)
CASE PRECISION_32BIT:
' Use standard matrix multiplication
MatrixMultiply(A, B, C)
END SELECT
END SUBThe system will detect the CPU type to enable optimizations specific to different 486 variants:
' CPU type enumeration
ENUM CPUType
CPU_486SX = 1 ' No FPU
CPU_486DX = 2 ' With FPU
CPU_486DX2 = 3 ' With FPU, higher clock
CPU_486DX4 = 4 ' With FPU, highest clock
CPU_PENTIUM = 5 ' Pentium or higher
END ENUM
DIM SHARED g_cpu_type AS CPUType ' Global CPU type
DIM SHARED g_has_fpu AS INTEGER ' Whether FPU is available
' Detect CPU type and capabilities
FUNCTION DetectCPU() AS CPUType
DIM cpu_type AS CPUType
DIM has_fpu AS INTEGER
' This would be replaced with actual 486-era CPU detection
' For modern testing, we'll use a placeholder
#IFDEF __FB_64BIT__
cpu_type = CPU_PENTIUM
has_fpu = 1
#ELSE
' Simple detection - this would be expanded in real implementation
' to check for actual CPU model using documented techniques from the era
has_fpu = TestForFPU()
IF has_fpu THEN
cpu_type = CPU_486DX
ELSE
cpu_type = CPU_486SX
END IF
#ENDIF
' Store in global variables
g_cpu_type = cpu_type
g_has_fpu = has_fpu
RETURN cpu_type
END FUNCTION
' Test for FPU presence (simple test)
FUNCTION TestForFPU() AS INTEGER
DIM fpu_available AS INTEGER
' This would be a real FPU test on 486-era hardware
' For modern testing, we assume FPU is available
#IFDEF __FB_64BIT__
fpu_available = 1
#ELSE
' Simple test that would be replaced with actual detection
' such as checking the FPU control word or attempting a simple calculation
ON ERROR GOTO no_fpu
DIM x AS SINGLE = 1.0
DIM y AS SINGLE = x / 3.0
fpu_available = 1
GOTO end_test
no_fpu:
fpu_available = 0
end_test:
ON ERROR GOTO 0
#ENDIF
RETURN fpu_available
END FUNCTIONTo ensure the correctness of the SIMD-like implementation, we'll create comprehensive test cases:
' Test SIMD-like operations for 8-bit precision
SUB TestSIMD_8bit()
DIM a_packed AS LONG, b_packed AS LONG, result AS LONG
DIM a1 AS BYTE, a2 AS BYTE, a3 AS BYTE, a4 AS BYTE
DIM b1 AS BYTE, b2 AS BYTE, b3 AS BYTE, b4 AS BYTE
DIM r1 AS BYTE, r2 AS BYTE, r3 AS BYTE, r4 AS BYTE
' Test Pack_8bit
a_packed = Pack_8bit(10, 20, 30, 40)
Unpack_8bit(a_packed, a1, a2, a3, a4)
PRINT "Pack/Unpack 8-bit Test:"
PRINT "Expected: 10, 20, 30, 40"
PRINT "Actual: "; a1; ", "; a2; ", "; a3; ", "; a4
' Test SIMD_Add_8bit
a_packed = Pack_8bit(10, 20, 30, 40)
b_packed = Pack_8bit(5, 10, 15, 20)
result = SIMD_Add_8bit(a_packed, b_packed)
Unpack_8bit(result, r1, r2, r3, r4)
PRINT "SIMD_Add_8bit Test:"
PRINT "Expected: 15, 30, 45, 60"
PRINT "Actual: "; r1; ", "; r2; ", "; r3; ", "; r4
' Test overflow handling
a_packed = Pack_8bit(250, 250, 250, 250)
b_packed = Pack_8bit(10, 10, 10, 10)
result = SIMD_Add_8bit(a_packed, b_packed)
Unpack_8bit(result, r1, r2, r3, r4)
PRINT "SIMD_Add_8bit Overflow Test:"
PRINT "Expected: 4, 4, 4, 4 (with overflow wrapping)"
PRINT "Actual: "; r1; ", "; r2; ", "; r3; ", "; r4
' Test SIMD_Multiply_8bit
a_packed = Pack_8bit(5, 10, 15, 20)
b_packed = Pack_8bit(2, 3, 4, 5)
result = SIMD_Multiply_8bit(a_packed, b_packed)
Unpack_8bit(result, r1, r2, r3, r4)
PRINT "SIMD_Multiply_8bit Test:"
PRINT "Expected: 10, 30, 60, 100"
PRINT "Actual: "; r1; ", "; r2; ", "; r3; ", "; r4
END SUBWe'll include benchmark functions to measure the performance improvements:
' Benchmark SIMD-like matrix multiplication vs. standard
SUB BenchmarkMatrixMultiply(size AS INTEGER, iterations AS INTEGER)
DIM a AS Matrix, b AS Matrix, c_std AS Matrix, c_simd AS Matrix
DIM start_time AS DOUBLE, end_time AS DOUBLE
DIM std_time AS DOUBLE, simd_time AS DOUBLE
DIM i AS INTEGER
' Initialize matrices
InitMatrix(a, size, size)
InitMatrix(b, size, size)
InitMatrix(c_std, size, size)
InitMatrix(c_simd, size, size)
' Fill with test values
FOR i = 0 TO size - 1
FOR j = 0 TO size - 1
a.data(i, j) = (i * size + j) MOD 100
b.data(i, j) = ((i * size + j) * 2) MOD 100
NEXT j
NEXT i
' Benchmark standard matrix multiplication
start_time = TIMER
FOR i = 1 TO iterations
MatrixMultiply(a, b, c_std)
NEXT i
end_time = TIMER
std_time = end_time - start_time
' Benchmark SIMD-like matrix multiplication
start_time = TIMER
FOR i = 1 TO iterations
MatrixMultiplySIMD_8bit(a, b, c_simd)
NEXT i
end_time = TIMER
simd_time = end_time - start_time
' Compare results for correctness
DIM errors AS INTEGER = 0
FOR i = 0 TO size - 1
FOR j = 0 TO size - 1
IF ABS(c_std.data(i, j) - c_simd.data(i, j)) > 2 THEN ' Allow small rounding differences
errors = errors + 1
END IF
NEXT j
NEXT i
' Report results
PRINT "Matrix size: "; size; "x"; size
PRINT "Standard version time: "; std_time; " seconds"
PRINT "SIMD-like version time: "; simd_time; " seconds"
PRINT "Speedup: "; std_time / simd_time; "x"
IF errors > 0 THEN
PRINT "WARNING: "; errors; " error(s) detected in SIMD-like implementation"
ELSE
PRINT "Results match between standard and SIMD-like implementations"
END IF
END SUBThe SIMD-like bit manipulation functionality will integrate with the following system components:
-
Matrix Operations (matrix_ops.bas)
- Enhanced matrix multiplication, addition, and elementwise operations
- Automatic precision selection based on operation and matrix size
-
Transformer Components (transformer_components.bas)
- Optimized attention mechanism calculations
- Accelerated feed-forward network processing
-
Model Operations (model.bas)
- Efficient embedding and token processing
- Optimized layer calculations
-
Benchmarking System (benchmark.bas)
- Performance comparisons between standard and SIMD-like operations
- Memory usage analysis
The implementation will proceed in the following order:
- Basic packing and unpacking functions for all precisions
- SIMD-like arithmetic operations for 8-bit values
- Optimized matrix multiplication for 8-bit values
- CPU detection and precision selection
- Remaining arithmetic operations for all precisions
- Integration with matrix operations system
- Performance testing and optimization
- Documentation of all functions
The SIMD-like bit manipulation component is considered software-complete when:
- Matrix operations show at least 1.5x speedup compared to standard implementation
- All operations produce numerically correct results within acceptable error tolerance
- Memory usage is reduced through packed representation
- Automatic precision selection correctly balances performance and accuracy
- Implementation works correctly on all supported CPU types
This design document provides a comprehensive blueprint for implementing SIMD-like bit manipulation in the GPT-2 BASIC project, enabling significant performance improvements within the constraints of 486-era hardware.