K-Means in Assembly
Clustering algorithm at register level
Overview
This was a Computer Architecture project at IST — implement K-Means clustering from scratch in Assembly, with a live visualisation on a simulated 32×32 LED matrix. No abstractions. No stdlib. Just registers and memory.
Stack
Preview
Add screenshot 1
Drop an image here
Add screenshot 2
Drop an image here
What I learned
- Understood exactly how high-level algorithms translate to register operations
- Managed memory manually with no safety net — pointer arithmetic by hand
- Implemented two versions: naive iterative and an optimised variant with precomputed distances
- Gained deep respect for what compilers do automatically
Build log
Struggles, findings, decisions, breakthroughs — the honest story.
No debugger worthy of the name
The only debugging tool was the register viewer. One off-by-one in a pointer calculation meant hours of staring at hexadecimal.
Division is expensive in Assembly
K-Means requires a lot of division for centroid updates. Replacing division with bit shifts where possible cut runtime significantly.
Precomputing distances halved iterations
The optimised version precomputes and caches partial distances. Sounds obvious in high-level code. In Assembly, implementing the cache structure was a week of work.
Fixed K=3 clusters
Generalising to arbitrary K would have required dynamic memory — impossible in the project constraints. Fixed K kept the code tractable.