brmlab

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Ledum ======

{{template>:project:infobox|
name=Ledum|
image=ledum:320px-ledum_palustre_bluehend.jpg|
sw=FIXME|
hw=FIXME|
founder=[[user:yokotashi]]|
interested=[[user:abyssal]]\\ [[user:bluebear]]\\ [[user:ccx]]\\ [[user:hexo]]\\ [[user:joe]]\\ [[user:prilezitostnypetr]]\\ [[user:rainbof]]\\ [[user:sachy]]\\ [[user:santiago]]\\ [[user:tma]]\\
|
status=active
}}

This project aims to design and develop a new central processing unit (CPU) with a primary focus on //correctness// and //object capabilities.// The design will prioritize formal verification techniques, ensuring the CPU’s functional correctness while introducing innovative approaches to resource management using object capabilities for improved security, efficiency, and modularity. 


===== Project Objectives =====

  - **Achieve High Correctness in Design:**
    * Use formal methods, simulation, and rigorous testing to verify that the CPU’s architecture is functionally correct.
    * Ensure that the CPU meets or exceeds industry standards for reliability and precision.
  - **Implement Object Capabilities Model:**
    * Integrate an object capabilities model into the CPU’s architecture to allow fine-grained, secure management of memory and I/O resources.
    * Ensure that resource access control is embedded at the hardware level to improve security by default.
  - **Enable Scalable Security Mechanisms:**
    * Design the CPU with scalable security features, leveraging capabilities to prevent unauthorized access and misuse of system resources.
    * Provide users with the flexibility to define and manage their own access control policies through object capabilities.
  - **Optimize Performance:**
    * Ensure that the CPU achieves optimal performance in terms of throughput, latency, and power consumption, without compromising correctness or security.
    * Ensure, that the CPU architecture can be parallelized to achieve IPC>1 including OoO execution, although to do so isn't primary objective. 
    * Balance hardware features for high-performance tasks with robust security measures for sensitive operations.
  - **Establish Robust Ecosystem Support:**
    * Develop comprehensive software toolchains and drivers to support the object capability model.
    * Collaborate with industry partners to ensure broad compatibility with existing operating systems and applications.


===== Project Scope =====

==== In-Scope ====

  * **CPU Architecture Design:** Define instruction sets, pipeline architecture, memory hierarchy, and integration of object capabilities.
  * **Formal Verification:** Apply formal methods to mathematically prove the correctness of critical parts of the architecture.
  * **Security & Resource Management:** Implement object capabilities as a mechanism to control access to system resources.
  * **Prototyping and Simulation:** Build prototypes and simulate the architecture to validate design decisions.
  * **Performance Evaluation:** Benchmark the new CPU's performance across several applications to assess trade-offs between correctness, performance, and security.
  * **Software Toolchain Development:** Develop and release supporting software tools, such as compilers, debuggers, and simulators, that work with the new object capability model.

==== Out of Scope ====

  * Development of end-user software applications or operating systems.
  * Manufacturing of physical CPU chips (to be handled post-design phase).
  * Integration into mass-market consumer devices (focus will be on specialized, high-assurance markets initially).

===== Workshops =====

As a part of our efforts, we have realized that different members of the team have different experience with various scientific and engineering fields and it would be very helpful to ensure that everyone has some basic understanding of all required topics. The workshops typically take place during the working group's regular meetings on Thursdays (see [[event:start]]).

If there is enough interest, we are streaming the workshops online using [[https://meet.jit.si/ledum-wg-meetup]]. We are also trying to get our A/V streaming and editing skills to a level that allows for publishing the recordings of the workshops. Any help with such endeavor would be more than welcome.

==== Streaming Setup in Brmlab ====

The public laptop available in the social room, clearly labeled "Brmlab", has some rudimentary setup for online streaming of Ledum Working Group Meetings. The online session can be setup as follows:

  - Locate the aforementioned laptop.
  - Find its power supply adapter.
  - Put the laptop on a table near the pack of cables hanging down from the ceiling roughly in the middle of the room.
  - Connect the power supply adapter to 230V socket and to the laptop.
  - Power up the laptop by pressing the power button located just left of the delete key which is in the top right corner of the keyboard and double-check it is not running only on the battery.
  - Connect a mouse to the laptop - it is really needed for any actual directing of the session.
  - Go to the audio mixing table - by the time of this writing, it is located by the 3rd window pair counting from the entrance
  - At the table, search for and pick up:
    * red/black USB device for capturing HDMI output 
    * blue USB-A to USB-A USB 3.0 cable
    * (probably black) HDMI cable of sufficient length (2m should be OK)
  - Get back to the laptop and connect the HDMI capture device to the remaining USB-A port of the laptop.
  - Start the Chromium browser and load the meeting URL (see above).
  - Grab the HDMI cable going from the projector just under the ceiling and connect it to the integrated HDMI port on the right hand side of the laptop (next to the power supply connector).
  - Power up the projector using the "Optoma" remote clipped to the pack of cables slightly above the table. You need to press the red power button in the top left corner twice and the red light on the projector should change to blue.
  - Ensure the system is configured to use the external projector as secondary / separate screen.
  - Move the Chromium browser window to the secondary screen and put it in the full-screen mode. Beware - without Fn-Lock, the F11 key puts the laptop in the Airplane Mode.
  - Start OBS Studio (it is installed).
  - If it asks for the permission to share a screen window, check it is the Chromium browser window you have just opened and allow sharing.
  - In the "Scene Collections" menu at the top of OBS Studio's window, check whether "LedumMeeting" is selected and select it if it is not.
  - Select the "Default" scene in the lower left corner of the window.
  - Ensure the laptop's internal camera located just above its display has its cap open.
  - In the sources list right to the scene selection of the previous step, check and ensure:
    * The "JitsiWindow" source shares the Chromium browser window opened earlier.
    * The "SpeakerCamera" displays the image from the front camera facing the director of the session (that is typically you).
    * The "HDMICapture" properly sees whatever you connect to it (typically use another laptop to double-check).
  - Now that everything is ready, click the "Start Virtual Camera" button in the lower right corner (fourth from the bottom). You may need to enter the password "brmbrm".
  - Go back to Chromium browser window and select the newly created "OBS Camera" as the primary video source for the Jitsi meeting.
  - Go back to OBS Studio and select the "Intro" scene and you are ready to go. 

==== Past Workshops ====

  * 2024-10-10 16:00 [[user:tma]] - Verilog I: Introduction to Verilog (CZ)
  * 2024-10-24 16:00 [[user:tma]] - Verilog II: Register Bank in Verliog (CZ)
  * 2024-10-31 16:00 [[user:joe]] - Lambda Calculus I: Introduction to Lambda Calculus (CZ)
  * 2024-11-07 18:00 [[user:tma]] - Verilog III: Advanced Verilog (CZ)
  * 2024-11-14 16:00 [[user:sachy]] - Assembler on Mainframes (CZ)
  * 2024-11-21 18:00 [[user:yokotashi]] - Introduction to Electronics (CZ)
  * 2024-11-28 16:00 [[user:tma]] - Verilog IV: Testbenches (CZ)
  * 2024-12-05 16:00 [[user:joe]] - Lambda Calculus II: Lexical Scoping and Evaluator Implementation (CZ)
  * 2024-12-12 16:00 [[user:ccx]] -- History of Capability Systems I (CZ)
  * 2025-01-09 17:00 [[user:hexo]] -- Adders and Multipliers (CZ/SK)

==== Planned ====


===== Design Topics =====
==== ISA Description ====
Warning: This part may change wildly at this stage.

=== Registers ===
   * 64 GPR 
   * upto 64 PTR (Pointer registers)
   * special registers (CS:IP and several configuration registers probably)
   * No flag register (flags are going either to another GPR or to a special 4-bits adjacent to every GPR), this should help future with parallelization

=== Pointers ===
   * Fat Pointers supported and tested by HW
   * Ultra Fat Pointers supported and tested by HW, can't be dereferenced outside the CS stored inside them

=== Tagging ===
   * All RAM and registers is tagged, so ALU knows which type it's operating on and pointer cannot be created freely
   * Types: int, uint, float in 4, 8 ... 64 bit lengths fit in vector 64-bit long; Fat pointer, Ultra fat pointer

=== SW-implemented services ===
   * scheduler
   * memory allocator
   * IO allocator
   * message broker
   * garbage collector
   * process creator

Notes:
# Any fiber can provide those services to others using it's resources. But the initial providers have all available resources and ability ru run privileged instructions if it's needed for their jobs.
# Process hierarchy, memory quota hierarchy and IO hierarchy are completely independent. 

Terminology
   * thread - X has asked scheduler to create it. X is it's parent and can see it's whole memory.
   * process - X has asked process creator to create it. Process creator is it' parent and can see it's whole memory. X is it's parent process in process creator's data structures only. X doesn't have access to it's memory. It has nothing to do with IO or memory quotas, they can be set with different granularity.
   * fiber - any thread or process
   * There may be more process creators. Therefore the same fiber may be viewed as thread (from it's process creator and it's parent threads) and as process (from another process under the same process creator). 
   * Channel - some way of communicate which is using a tagged handle normal fiber can't create from integer (similar restriction like a FP has)

== scheduler ==
   * has HW capability to change settings of the HW scheduler in the CPU
   * shouldn't be GCed probably (although it's data structures may utilize weak pointers)
   * works on fibers (doesn't distinguish between process and thread)
   * must know CS:IP and time-quota of every fiber
   * contains fiber hierarchy
   * fiber can push to it (via message containing FP) what childs it wants and how to divide it's time between them. Those information must be converted to absolute values by the scheduler, therefore they can't be used directly from fiber's memory, because that would trigger descent through tree and recalculation for every rescheduling.
   
== memory allocator ==
   * starts with FP to almost all memory (except memory given to other SW services)
   * has information about what memory is empty and used
   * has information about memory quotas
   * when asked through some channel if can either allocate memory and return a FP or "create"#1 a new channel with some part of quota of the calling channel and return the new channel. It can shuffle the quota between already created channels to. 
   * it manages similar hierarchic structure as scheduler or process creator, but there are channels and their associated quotas in the tree

#1 message handler will do the creation itself, but the channel will be between allocator and anyone who has the complementary handler given to the original caller

== IO allocator ==
   * it has capabilities to communicate with the IO somehow (via messages and DMA to FP?)
   * it has information about which channel has rights to use what part of IO space
   * any channel owner can ask for creating another channel with less rights -> therefore the structure is hierarchic
   * any channel owner can ask for destruction of channel under it in the hierarchy 
   * any channel owner can ask it to do some IO and if it has enough rights, that IO will be done
   * there may be more fibers behaving as IO allocator - it enables virtualization (lower allocator asks the higher one) and having non-HW IO capabilities (like to send a piece of memory to IP:port via TCP or UDP)

== message broker ==
   * creates channels and tags their handles. It may create 4 handles at once differing in the lowest 2 bits. Each pair of them is for one way of communication. The lowest bit may specify if the handle is sender or reciever. These handles are tagged, therefore no one else can create them.
   * destroys channels after being asked to do so.
   * it operates the mesasging HW. 
   * TODO: specify how the hw and messages itself will work
   * TODO: How to ask a message broker for new handles with no handles? Handle 0 may be for communincation with mesage broker and working even without the proper tag? Another instruction?

== garbage collector ==
   * collect unused memory
   * ignores the FP to the whole RAM in memory allocator
   * collects unused handles to communincation channels too (TODO: somehow)  
 
Weak pointers will be needed probably.

== process creator ==
   * from the scheduler's point of view it is parent of all processes (fibers) running under it
   * creates and destroys a processes when asked
   * creates channels between parent and child process 
   * stores process hierarchy similarly as scheduler stores fiber hierarchy and memory allocator stores quota hierarchy

There may be more process creators. 
The main reason for existence of process creator is possibility to create a child without being able to travel down through it's memory. Process creator will have this ability of course, but it should be small, simple and well audited.

==== Inctructions and assembly ====

  * Fixed-length instructions (64 bit) - decoder simplicity
  * Instructions aligned to 64 bit addresses - decoder simplicity
  * First 8 b is an opcode
  * Macro-instructions (???)
    * Single instruction is unrolled into multiple instuctions by instruction decoder and then executed by the CPU as if coded by hand
    * Increased code density - things like clearing multiple registers by single "XRM 1,15" (Xor Register - Multiple reg_n,reg_m) unrolls into sequence XR 1,1,1 XR 2,2,2 ... XR 15,15,15 (Xor Register reg_result,reg_i,reg_j)
    * Hardcoded in CPU wiring
  * Supervisor Call Instructions
    * Instruction passed outside of fiber/CPU and result passed back into specified register
    * Raw-content register communication only, no way to pass memory
    * Things like:
      * Get current timestamp from BIOS or whomever
      * Power management - tell the motherboard to sleep/turn off
      * lowlevel ioctl used by hardware broker task
      * VM communication?
      * Allow itself being debugged?
      * Message passing between fibers and basic services
      * Inter-CPU communication (multicore, multisocket)
  * Supported instruction set
    * Derived from real-life massive applications by statistical analysis of used instructions
    * Go along Parret rule that 20 % instructions do 80 % work - optimize that, ignore specialties
    * Semaphores instructions
      * Compare-swap
      * ST0 - Store 0 or set condition code; ST1 - Store 1 or set condition code - if the memory was already non-zero (non-one), soft fail - atomic locking 
    * Vector processing
      * Register treated as a vector of 4/8/16/32b long values
    * Constant-time processing
      * Compare-sort - order 4 registers by value in HW
      * Hashing primitives
      * Encrypt/decrypt primitives
  * Inctruction naming convention to be defined
  * Hex representation and opcode allocation to be defined
  * Unused opcodes for future use


==== Electronic Circuit Design ====

==== Integrated Circuit Design ====

==== Tooling ====

==== Miscellaneous ====
=== Things to read ===
== Optimizations ==
- Compressed pointers: https://shipilev.net/jvm/anatomy-quarks/23-compressed-references/

- Read barriers pro concurent scavenger: https://blog.openj9.org/2019/03/25/concurrent-scavenge-garbage-collection-policy/ + HW support https://www.ibm.com/support/pages/pause-less-garbage-collection-java-ibm-z https://www.ibm.com/docs/en/zos/3.1.0?topic=ixg-ieagsf-guarded-storage-facility-services

- Chinual: https://tumbleweed.nu/r/lm-3/uv/chinual.html

- https://pqnelson.github.io/org-notes/comp-sci/lisp/machine/i/architecture.html
===== Current Progress =====

==== Tooling ====

{{ :project:ledum:rawaketa-l8b-breakout.png?direct&400|}}

{{:project:ledum:rawaketa-l8b-assembler.png?direct&400 |}}

As a proof-of-concept an assembly language compiler and IDE support was implemented for a very simple Harvard architecture 8-bit CPU. A graphical emulator for the same simple CPU was created as well. The aim of these tooling efforts is to provide a unified framework for creating custom instruction sets including their assemblers and emulators.

<WRAP clear></WRAP>

==== Simulator GUI ====

{{ :project:ledum:qasireu-lqabec-socm1-gesicht.png?400|}}

A simple GUI was developed for simulating a SOC written in Verilog.

<WRAP clear></WRAP>

~~META:
status = active
&relation firstimage = :project:ledum:320px-ledum_palustre_bluehend.jpg
~~