Thinking ahead: Supporting multicore CPUs

How about a simple (bubble?) integer sort? I say simple because efficiency is not the major goal.
Should read & write lots of memory; time can be varied by amount of data and its initial state (could be best/worst-case for sort type); only C library calls to write output?; result easily checked. And I am sure there are C examples around – just a matter of enabling it to run from RMA.

Depending on how the RMA code is invoked, maybe just have a SWI to write a “random” pattern to a big memory claim, then bubble sort it? Light to be dead easy to code up.

Any ‘Random’ data used must be repeatable, eg by having the same seed for each test run, otherwise the sort times will be different!

That’s why I put random in quotes – seed the random number generator with a known value, should provide the same data set each time.
Failing that, just count from 0 to 255 in a loop. Over and over. Then sort that. ;-)

Something to make you smile while you’re working on getting multicore stuff working smoothly…

…we’ve all been there, right? Get something ready, toss it over to the printer, then realise you need to shell out for some more bottled unicorn tears in order to get results that look like they’re supposed to look.

Remember.

It could be worse.

(full size)

Proposed candidates that can can use large amounts of memory, don’t rely on SWI’s, don’t use too much time with each sweep through the memory, thrash the datacache(s), and are easy to program: Eratosthenes, radixsort, or an automaton of the 90’s such as Hodgepodge. To see if results are correct, (a) should return the same number of primes each time, for (b) the array can be filled with random numbers with a fixed seed, return CRC of the result; (adapt the algorithm to use 32/64/96 etc integers to get more passes); © can be calculated in 4 directions and should give the same result (CRC) each pass.

Fwiw, an ultra simple sieve algorithm in 40 instructions. Checks 32M numbers in ~1 sec on RPI 1
Can be improved a lot but the object is datacache-thrashing and small codesize, not speed.
190 DEFPROCasm:LOCAL result,sieve,max,ie,ptr,word,byte,index,noofprimes,quadra
191 FORpass%=0TO2STEP2:REM use O% and different pass% values to get position-independance, etc
192 result=0:sieve=1:max=2:ie=result:ptr=result:word=3:byte=4:index=byte:noofprimes=5
193 quadra=noofprimes
194 REM MAXIMUM size 1<<32-1, call with R1=base address of sieve workspace,
195 REM and R2=#numbers to explore(<1<<32), returns no_of_found_primes in R0
196 REM so in BASIC, B%=sieve_base%, C%=no_of_numbers%, DIM B% C%>>>1
197 REM and then call with: noofprimes%=USR
198
200 P%=code%:[OPT pass%:.primes MOV ie,#0:MVN word,#0
211 .fill CMP ie,max,LSR#1:STRLO word,[sieve,ie]:ADDLO ie,ie,#4:BLO fill
212 MOV ptr,#1:MOV quadra,#1:MOV word,#0:.loop1
213 ADDS quadra,quadra,ptr,LSL#2:ADDCC ptr,ptr,#2:ADDCCS quadra,quadra,#4
214 LDRCCB byte,[sieve,ptr,LSR#1]:CMPCC quadra,max:BHS endloop1
215 CMP byte,#0:BEQ loop1:MOV index,quadra
216 .loop3 CMP index,max:STRLOB word,[sieve,index,LSR#1]
217 ADDLO index,index,ptr,LSL#1:BLO loop3:B loop1
218 .endloop1 MOV ie,#0:MOV noofprimes,#1\for prime= ‘2’
219 .count CMP ie,max,LSR#1:BHS endloop4
220 LDR word,[sieve,ie]:ADD ie,ie,#4
221 TST word,#1 :ADDNE noofprimes,noofprimes,#1
223 TST word,#1<<8 :ADDNE noofprimes,noofprimes,#1
224 TST word,#1<<16:ADDNE noofprimes,noofprimes,#1
225 TST word,#1<<24:ADDNE noofprimes,noofprimes,#1:B count
226 .endloop4:MOV result,noofprimes:MOV 15,14:]
229 NEXT:ENDPROC

Thanks for the suggestions – in the end I went with a hashtable-based radix sort, pilfered from here.

After making a couple of quick tweaks to pscramble, the threaded radix test reports a failure within a matter of seconds, so I think I’m in a pretty good position to test the areas I’m interested in.

All of the SMP code (apart from OS_Memory 19, which is still WIP) is now in CVS. This includes the kernel changes (on a “SMP” branch in CVS), HAL changes (for BCM2835, OMAP4, iMx6 – also on “SMP” branches), and the SMP module (at mixed/RiscOS/Sources/Programmer/SMP). To build the code yourself:

1. Build a ROM containing a HAL + Kernel from the SMP branch. Ensure high processor vectors are enabled (the SMP module patches itself into a hardcoded address in the kernel workspace)
2. Build and run the SMP module

There are a couple of test apps in the SMP module sources which you can use to check things are working (although if the SMP module doesn’t crash or throw an error then you’re probably OK). Also in addition to the docs in the SMP module sources, there’s a new docs folder in the kernel to cover some of the HAL/kernel-level changes.

Compared to this post, notable changes are:

• The IRQ handling has been changed so that there’s one global IRQ dispatcher instead of one per core. So core affinity with OS_ClaimDeviceVector & OS_ReleaseDeviceVector is no longer an issue. However, see the SMP module docs for a gotcha.
• Service_PagesUnsafe / Service_PagesSafe is now dealt with safely, so dynamic areas which claim specific pages shouldn’t run the risk of crashing the system (this is the radix sort / pscramble testing I was talking about above).
• OMAP4 and iMX6 are now supported, although since OS_Memory 19 isn’t ready yet you can expect some instability on SATA-based systems (iMX6/OMAP5/Titanium)

My immediate plans for the future are to finish OS_Memory 19 (+ associated DMAManager/AHCIDriver/SATADriver changes), and to add OMAP5 support (necessary to test SATADriver).

excellent job Jeffery can’t wait to test it on Omap 5432evm

Opps second core

Amazing work. I can’t believe that RISC OS is moving to a proper scheduling kernel. I’m sure long term, this will make RISC OS far more speedy and robust for every day use.

Long live RISC OS.
:-)

Amazing work.

Absolutely.

This news sounds amazing. Making RISC OS work on more than one core has always been thought of as a really difficult, large project. Many of the RISC OS folk I know wondered whether ‘Jeffrey Lee’ could not be a single person, but must be a syndicate. Then someone told me that they had actually met ‘Jeffrey Lee’ and so now I think he is a single person, but has a multi-brain with all ‘brain cores’ working simultaneously and harmoniously to produce his amazing work.

a really difficult, large project.

It is.
But I think what helps is to have a clear objective (ie don’t ask the internet!), get the groundwork sorted first, and then do incremental steps towards the end goal.
It probably also helps that it is one person working on this as he knows what state the system is in at any given time of development. I’ve sometimes wondered with development teams how they manage to tackle complex low level stuff and stay in sync with each other…or maybe this explains why kernels alone take up megabytes these days? ;-)

his amazing work.

Was that ever in doubt?!

(I’ve read some of the docs on multi core programming…uh…is there a For Dummies version? (translation: it’s bloody complicated))

So, I have this friend that doesn’t know how to fetch a branch (or anything) from CVS. Any pointers?

Rick, how much do you know? A starting point could be looking for information on concurrent systems. PMT systems are a good place to start.

A simple clean slate PMT “kernel” is probably a lot easier to put together than a co-operative one. However taking an established system such as RISC OS and adding better PMT and on top of that SMP support is nothing short of sorcery. I really look forward to giving this a try.
When I started seeing comments on CVS appearing with SMP in them I thought it stood for something else that I wasn’t aware of. Jeffrey, you have performed an amazing task.

So, I have this friend that doesn’t know how to fetch a branch (or anything) from CVS. Any pointers?

The Beginner’s guide to ROM builds page has information about fetching the sources from CVS.

To fetch a component from a specific branch, you want to use the -r option with the cvs checkout or update commands. This page also has some useful bits and pieces I’ve been collecting over the years; the first section is mostly concerned about setting up CVS write access, but the rest is applicable to any ROOL CVS user.

Another way of fetching things from the SMP branch would be to make local changes to the products file, so that the checkout script will do all of the legwork.

However taking an established system such as RISC OS and adding better PMT and on top of that SMP support is nothing short of sorcery.

I’d say it’s more akin to running a SMP/PMT microkernel alongside the single-core RISC OS kernel, and slowly allowing the SMP/PMT features to seep into the RISC OS world. The downside is that the SMP code isn’t allowed to interact with most of the OS, but the upside is that there’s minimal negative impact (compatibility issues, etc.) on the single-core world.

I think there are a few important tasks that need to be completed before we reach the point where the code is “production ready” – i.e. modules can easily use threads, and arbitrary modules can be made SMP-friendly:

• OS_Memory 19 / DMA safety (in progress)
• MP-safe OS_Heap and OS_(Change)DynamicArea
• Wait object support in thread scheduler (currently it only supports pollwords, which are very RISC OS but also very inefficient)
• Module header extensions to allow modules to identify themselves as being MP-safe (currently there’s a whitelist which must be managed manually)

It was fetching the branch that was causing some confusion… but I forgot to pack it. The way I have things set up I’d have to grab the tarball then unpack it using RO. My source is stored on an NTFS formatted USB drive connected to an SBC running Armbian, and accessed by me using NFS and Sunfish. It works well as long as Sunfish is set up right.

I agree with your approach. I certainly don’t have the right knowledge but it’s the way I was thinking it could work.

I do have to ask, will it be able to affect task windows, or more specifically what they are running? I’d love to see an improvement to their rudimentary multitasking. It seems to have very coarse granularity.
I see that the finer points of the thread scheduler are still a TODO, but what’s really been interesting me is the CPU intensive non graphical applications.

e: I give RO an absolute flogging so I’d be happy to try it on my Pi3. (this).

I was wondering about this too can you just download the CVS tarball put it in a folder then use the unpacked tarball as a local copy of the repository in the Risc OS CSV client??
if so (the Big question)how??

I do have to ask, will it be able to affect task windows, or more specifically what they are running? I’d love to see an improvement to their rudimentary multitasking. It seems to have very coarse granularity.

There are a couple of aspects to this.

For threads which want to access application space, we need a way for each core to have different wimp slots mapped in. The easiest way of supporting this will be to implement support for ASID-based task swapping (although, implementing ASID-based task swapping itself isn’t entirely trivial – but it will be trivial to use in SMP setups). However, the main thread of any app will still be restricted to running on the primary core (since 90% of the OS is designed around CMT)

But since a task window is a PMT wrapper for single-tasking apps, code running within a task window isn’t likely to try interacting with the Wimp or other tasks at all. This means it should be possible to provide some degree of automatic multi-core use, as described here. Doing it properly would require the SMP module to support code taking over full control of a core (blocking regular threads and interrupt handlers), so that the core can safely switch to the stripped-down memory map. But it should be possible to prototype the idea using a stripped-down version of the module (and for a prototype version you could get by without ASID-based task swapping).

I was wondering about this too can you just download the CVS tarball put it in a folder then use the unpacked tarball as a local copy of the repository in the Risc OS CSV client??

As it says on the downloads page, the CVS repository archives require the use of a CVS server. I.e. you download the archive, extract it, run a local CVS server instance (pointing to the extracted archive), and then point your CVS client at it your local CVS server. In most cases you’re better off just pointing your CVS client directly at ROOL’s CVS server.

I think I have it sorted. It’s downloading now. At least my internet connection won’t be putting any load on the ROOL server. hopefully “checkout BCM2835Dev -r SMP” is what was needed to do it correctly with the Perl script?

Does it need anything besides the compiled ROM to be functional in the sense that it can boot?

There’s probably no way of telling anything is going on beyond the test programs, right?

hopefully “checkout BCM2835Dev -r SMP” is what was needed to do it correctly with the Perl script?

No; that will try selecting the “SMP” tag/branch of the BCM2835Dev product file. I guess it must have defaulted to the main branch if it’s working.

Once you’ve used checkout to download the sources, you can do the following:

# Fetch SMP module sources
cvs co mixed/RiscOS/Sources/Programmer/SMP
# Switch to SMP version of HAL
cvs up -RdP -r SMP mixed/RiscOS/Sources/HAL/BCM2835
# Switch to SMP version of kernel
cvs up -RdP -r SMP castle/RiscOS/Sources/Kernel

Does it need anything besides the compiled ROM to be functional in the sense that it can boot?

The system should boot just fine. However the SMP module currently isn’t part of the ROM image, so you’ll have to build and run that manually (run the Mk script from its source folder, then look in the ‘rm’ folder for the output). It will actually build both “debug” and “non-debug” versions of the module – that just relates to whether debug symbols are included, there’s no functional difference between the two.

There’s probably no way of telling anything is going on beyond the test programs, right?

*SMPMetrics and *SMPThreads can be used to check the state of the system. The SMP makefile currently has DEBUG enabled by default (not to be confused with the debug build that the Mk script creates!), so you’ll also get lots of debug spam output to the screen when the module starts.

I just built the source I grabbed yesterday. Had lots of unrelated problems with the build system. Some old versions of programs had snuck in and caused chaos.

OS image is built and running, and so is the module. SMPMetrics and SMPThreads report information back.

You mentioned a whitelist. Is it compiled in or an external list held somewhere?

The whitelist can be edited via a couple of the SMP SWIs. Read the docs!

Registration/deregistration is done on a per- SWI chunk basis, since that’s the same granularity on which SWI handlers operate. So to mark a module’s SWIs as being MP-safe you’d first find its SWI chunk base (pick a SWI, round down to multiple of 64) and then specify a bit mask of which SWIs within the chunk to enable. Then the SMP module will scan the module list and make a note of the corresponding handler address + private workspace pointer.

This is a bit of a curly question. Do you think UnixLib pthreads could ever support SMP or even better PMT by using this micro kernel, or a descendent of it at least?