Code Performance Estimation

In the past few weeks we have made a significant amount of progress towards our goal. I've finished up all of the mathematics, and most of the software design architecture. Luke has been working on a different portion of the project, and I'm sure he will post up here soon about that.

For our software, the critical portion is the main control loop that keeps the quadrotor flying at the desired attitude (roll, pitch, yaw) and altitude. It is essential that this control loop operates fast enough to respond to disturbances. From my research into what other quadrotor groups have done I have found that 50Hz to 75Hz is sufficient for flying. So for our project we need to analyze our system and determine if we can achieve the desired rate.

The first component to consider is the inertial measurement unit (IMU). The IMU that we have selected is the CHR-UM6-LT IMU. From the datasheet, it can output at up to 300 Hz. On the output we have the ESCs that control the motors. These expect a control pulse every 20ms, so that is on update rate of 50Hz. Most stock components can run with a slightly faster update rate, and we can select ESCs that are designed for a faster rate. In any case, we have guarenteed support for 50Hz updates with the hardware we have.

Now we need to consider the software control loop. I've broken the math into three blocks: attitude control, altitude control, and motor control. The attitude control block and altitude control block can be done in parallel, and their output fed into the motor control block. Luke and I will be writing the code in Propeller Assembly using the Float32 floating point library.

The Float32 documentation includes timings and space requirements for each of the mathematical functions. If we count the operations required for each block we can then calculate an estimate of running time and space.

First, we have to count up all of the operations so we know how much math we have to do:

	Quantity	+	-	*	/	cos	sin	asin	acos	atan2	sqrt	quat*	Sum
	Moment	1	6	20	11	3	4	0	2	2	0	3	52	ops
	Altitude	3	1	4	1	0	0	0	0	0	0	2	11	ops
	Motor Speed	14	10	18	10	0	0	0	0	0	4	0	56	ops
	Sum	18	17	42	22	3	4	0	2	2	4	5	119	ops

Our control loop has 119 mathematical operations. The number sounds small, but it is slightly misleading. In the next table we see that the time to execute an addition or multiplication is much less than it is to calculate arcsin or arccos. For quaternion multiplication we assume that one multiply has 6 floating point additions, 6 floating point subtractions, and 16 floating point multiplies. This follows from the quaternion multiplication formula. In summary, since we have the number of each operation, we can calculate the total times:

	100 MHz	+	-	*	/	cos	sin	asin	acos	atan2	sqrt	quat*	Sum
	Time (uS)	4	4	8	11	78	75	261	265	117	174	225
	Moment	4	23	168	116	234	298	0	531	234	0	675	2283	uS	438	Hz	2283	uS
	Altitude	11	4	34	11	0	0	0	0	0	0	450	509	uS	1964	Hz		uS
	Motor Speed	53	38	151	106	0	0	0	0	0	694	0	1042	uS	959	Hz	1042	uS
	Sum	68	65	353	232	234	298	0	531	234	694	1125	3835	uS	261	Hz	3326	300	Hz
														w/o Parallel			w/ Parallel

Our estimates show that we can have an inner control loop of 260Hz, and if we parallelize the moment and altitude calculations then we can get about 40Hz faster. Also of interest is that the quadrotor control loop has a response time of 3.3milliseconds. For reference, the average human reaction time is roughly 200milliseconds (source).

Finally, we are interested in code size. The floating point library has a number of required support functions that do things such as convert to and from floating point, compare floats, and so on that require space. We also assume that 4 longs on average are used to setup each operation. This gives us:

	(w/ 4 extra)	+	-	*	/	cos	sin	asin	acos	atan2	sqrt	quat*	Float	Trunc	Cmp	Pack	Upck	Extra
	Size(longs)	24	6	18	19	2	45	36	5	25	28	15	13	17	22	25	42	30		Ops + Support
	Moment	28	30	98	63	14	61	0	49	33	0	27	13	17	22	25	42	30		552
	Altitude	36	10	34	23	0	0	0	0	0	0	23	13	17	22	25	42	30		275
	Motor Speed	80	46	90	59	0	0	0	0	0	44	0	13	17	22	25	42	30		468
	Sum	96	74	186	107	14	61	36	13	33	44	35	13	17	22	25	42	30	848	1295
																			Sum w/o dup.

So, if we were to do each instruction in sequence then it would take approximately 850 longs. Unfortunately, a Propeller cog only has enough memory for 496 longs. If we break it into sections then the altitude and motor calculations will fit into a single cog, but the moment block is too big. Some optimizations will probably be able to reduce the size to fit.

All in all, the code performance estimates are looking very promising. We should be able to achieve 100Hz update rates without too much trouble. The actual programming is unlikely to pose a challenge since we have the equations laid out in the exact order necessary for implementation.

Many have been asking if we are flying yet. No, sorry, we are not. Both Luke and I have been working full time on this, but there are many details to be concerned about. We are getting closer though. In the next week I plan on working on the thrust/torque test stand, and once that is done I'll start programming the control loops and the like.

The current version of the tables in this post can be found at this link.