Spot the possible optimisation

beny1949

Senior Member
I dont know if anyone remembers, but last year about may/june time, i was working on a micromouse. things didn't go so well at the competition, but i have been having another go and things are looking much better now in the fact that my mouse now works!

The main issue with it now is that it runs very slowely when trying to do the bellman flood fill algorithm.

I was wondering if anyone can see any way that I could shorten this loop whilst performing the same function. this loop may have to be run over 100 times when it gets to the middle of a maze, so even shaving a few microseconds here and there will make a huge difference to the overal time taken

The loop goes through an array of 256 and checks that each cell has a value which is one more than its lowest neibouring cell. there is alot more information about this at: http://micromouse.cannock.ac.uk/maze/solving.htm

Here is the code:

Code:
	for FloodP = $00 to $FF  
		
			'get flood data
			hi2cin FloodP,(FloodD)
			Temp2 = FloodD
		
		
			'get wall data for the current cell
			read FloodP,WallD
					
			Temp1 = WallD & $01 'North
			if Temp1 = 0 then
				let WallP = FloodP + 16 'point north
				hi2cin WallP,(Temp1) 'read the flood value
				if Temp1 < FloodD then
					let FloodD = Temp1 + 1
				endif

			endif
		
			Temp1 = WallD & $04 'East
			if Temp1 = 0 then
				let WallP = FloodP + 1
				hi2cin WallP,(Temp1) 'read the flood value
				if Temp1 < FloodD then
					let FloodD = Temp1 + 1
				endif
			endif
	
			Temp1 = WallD & $10 'South
			if Temp1 = 0 then
				let WallP = FloodP - 16
				hi2cin WallP,(Temp1) 'read the flood value
				if Temp1 < FloodD then
					let FloodD = Temp1 + 1
				endif
			endif
		
			Temp1 = WallD & $40 'west
			if Temp1 = 0 then
				let WallP = FloodP - 1
				hi2cin WallP,(Temp1) 'read the flood value
				if Temp1 < FloodD then
					let FloodD = Temp1 + 1
				endif
			endif
			
			hi2cout FloodP,(FloodD)'write the number which is one bigger than the nearest cell
			
			if Temp2 != FloodD then: Let Change = 1: endif
	
		
		next 'go and look a
If anyone needs anymore details let me know. I am not sure really how much background anyone would need to be able to suggest improvements.
 

hippy

Technical Support
Staff member
I don't see any obvious scope for optimisation so it might have to be algorithm / technique design which changes.

Just realised the X1's only have 128 bytes of scratchpad, so the italicised here isn't particularly useful at the moment ...

If you can use the 256 byte scratchpad rather than external Eeprom that would speed things up considerably.

It may be possible to dump current scratchpad to Eeprom, load it with flood data, process and save that and reload later and still save time as there is a lot of processing to be done. Premature Eeprom burnout is the price you'd have to accept, or use 256x8 I2C RAM for the temporary copy.

The 40X2 can work as an I2C Slave so one running a "Do:Loop", do nothing program should act as a 256x8 I2C RAM as actual I2C RAM seems hard to find these days.

You could also use the 40X2 as the flood fill processor. Dump the initial data to that, tell it to process, and when you come to read later it will have the results you want ready and waiting. You can run that at 20MHz and I'd be tempted to try overclocking it to 24MHz/32MHz.


I'd also consider over-clocking all PICAXE's in the system.

If I recall right, any PICmicro/PICAXE set for running from an external crystal/resonator can be driven by an external oscillator module instead, so you'd only need one module for the entire board ( and some careful tracking ). As X1's / X2's have selectable clocking they'll all revert to 4MHz for programming.

If someone has a frequency generator or some oscillator modules it would be interesting to see how far the 28X1 and 40X1 can be over-clocked. Sparkfun pushed a 16F873A to 32MHz without even bothering with the XTAL capacitors. 32MHz is handy because it means serial comms will still work with other PICAXE's, but no reason not to strive higher for fastest operation. I2C shouldn't really care no matter what peculiar value is used, 33.8688MHz crystals are a common slavage from PC cards.

http://www.sparkfun.com/commerce/present.php?p=Overclocking a PIC

Another possibility is to use a non-PICAXE slave for the flood-fill part of the operation.
 

beny1949

Senior Member
Thanks very much Hippy!

I am actually using I2c Ram, i have a couple of PCF8750P's which i got from Rev-ed some time ago, kind of handy seen as they dont have them at the moment!

I have spent some time tring to think of another way to do this, which a picaxe can handle, but i think i am going to just have to wait for the X2's to go any faster. I am currently running at 16mhtz. Overclocking to a non standard/supported speed might be a bit of an issue for me currently as I am using the servo command. switching to an interupt and pulse out isn't much hassle having said that.

A quick question about the RAM, in the data sheet, it says that the maximum clock speed is 100Khtz. I was running it at that speed, but i have started to run it at 400Khtz. Is it safe to push it further, and is there anything i can do to make it more reliable at high speeds?


Thanks for your advice,

Ben
 

Dippy

Moderator
I was doing something using FRAM to hold my 'arrays'. The faster clock speed had only a sligt effect in my application as most of the delay was overhead involved in the actual command.
Also had to reduce the value of the pullups.
 

hippy

Technical Support
Staff member
At least with I2C RAM you cannot damage it so I'd simply try writing and reading changing bit patterns to see when it falls over then back-off. I don't think there's a lot to be done to make it more reliable at high speed other than keep the capacitance low and tweak the pull-ups. Watching the bus and signal slew on a scope may be the best trial and error method.

Code:
Do
  b0 = b0 * 2 : If b0 = 0 Then : b0 = 1 : End If
  For b1 = 0 to 255
    Hi2cOut b1,(b0)
    b0 = b0 + 1
  Next
  For b1 = 0 to 255
    Hi2cIn b1,(b2)
    If b2 <> b0 Then : SerTxd( "Oops - Failed !" ) : End If
    b0 = b0 + 1
  Next  
Loop
I can appreciate the issue with non-standard / over-clocked speeds and Servo. One approach may be another 28X1 I2C slave handling the Servo commands and perhaps other I/O ? That can run at 16MHz, the main controller at anything providing I2C works. I2C handily sidesteps the mismatched SerIn/SerOut baud rate issues.

The X1's auto-adjust to keep Servo running at the right speed regardless of crystal so there may be somewhere in SFR to poke to allow non-standard speeds and correct servo refresh operation.

Massive parallelism using multiple PICAXE's is the key IMO for maximimising throughput in a PICAXE system but not always cheap and it does require considerable design effort at times. It's often easy and inexpensive to throw in another PICAXE-08M to work as a front-end or back-end for wireless, serial or servo handling and to overcome delays like reading DS18B20 temperatures, but more complicated sub-systems take more effort, require higher-end PICAXE's and there's a limit to scaleability.

Maybe a dual-PICAXE system where the slave starts to calculates the flood-fill as a square is entered and by the time the master needs to use that information it will have the data ready ? It only needs to pass back a single byte saying which way to go.
 
Last edited:

Brietech

Senior Member
I know it is a bit blasphemous on this forum, but if all you genuinely care about is speed, and you aren't limited to a Picaxe, I have a Basic-X 24p chip you could have for the cost of shipping (which is probably pretty low, even though I'm in NYC). It has the following specs:

Speed 83,000 Basic instructions per second
EEPROM 32K bytes (User program and data storage)
Max program length 8000+ lines of Basic code
RAM 400 bytes
Available I/O pins 21 (16 standard + 2 serial only + 3 accessed outside standard dip pin area)
Analog Inputs (ADCs) 8 (8 of the 16 standard I/O pins can individually function as 10bit ADCs or standard digital I/Os or a mixture of both)
Serial I/O speed 1200 - 460.8K Baud
Floating point math 32bit x 32bit floating point math built-in
Programming interface High speed Serial
Physical Package 24 pin DIP module


I think they normally cost about $50 (+ shipping from the states), but I've had this lying around forever and could never think of anything fun for it. It should chew through your calculations in a blink, without being too much more complicated to program.
 

beny1949

Senior Member
That would be very kind of you indeed!!

The next competition for this mousy is minos 08 which is this weekend, so i guess its no good for then, however i am very keen to get this mouse working to its full potential!

If you are sure that you do not have a use for your basic X, I am sure that would make a great co-processor!

Ben
 

hippy

Technical Support
Staff member
If you're not sticking entirely with the PICAXE there are many more options available. The Parallax Propeller will give you eight processors on one chip, equivalent of 130,000 basic instructions per second ( plus 24MIPS Assembler ) per processor. So 50 times the oomph of a 16MHz 40X1 in total and as all data is in shared 32KB Ram almost zero comms overhead. $13+I2c Eeprom.
 
Last edited:

BCJKiwi

Senior Member
You've not indicated what i2c bus speed you are using nor which PE version.

There are issues with the i2c commands in earlier versions of PE which did not in fact run the i2c bus at the speed selected but always in slow but this was fixed with PE 5.2.0

If you are are only running the bus at 100 (slow) then there will be room for improvement by running the bus faster (provided the external eeprom you have supports it of course).
 

Dippy

Moderator
Going to another chip or compiler is pretty bloomin' obvious. I didn't mention it as this is a PICAXE forum. So keep the free advertising to a minimum eh?
 

beny1949

Senior Member
BCJKiwi,

I am running a PCF8570P RAM chip, which according to the data sheet is only upto 100Khtz, But i am running it at 400K at the moment without having any problems. I think I am now past the point of being able to make any changes for this weekend, after all i do have a worker!

thanks very much,

Ben
 

Dippy

Moderator
beny: "...after all i do have a worker!"

- if you've got got a worker, then get him to do some work and you can do your project.

Do you have a butler as well?
 

beny1949

Senior Member
no unfortuately not, although a buttler could be classed a worker.

Thanks all the same :)

Dippy:" this is a PICAXE forum."
 
Top