Introduction
Project Headline
A reconfigurable network of interconnected communicating MCUs to easily support inter-MCU communication and distributed computing.
Project Description
We designed a pluggable instant messaging system that communicates over the microprocessors. The microprocessors are connected in a line, each processor connected on either side to a single microprocessor. We can connect any of the microprocessors in any order we desire and the microprocessors will automatically adapt to their new conditions and route messages appropriately. Furthermore, microprocessors not directly taking part in the actually instant messaging may have to forward/route messages from one end of the conversation to the other. While our budget only allows for 2 to 3 microprocessors, our system would currently work with up to 7 microprocessors laid out in a line. While the instant messaging application isn’t particularly useful, we demonstrate an intra-MCU communications protocol that has the capability for simultaneous intra-MCU communication with no contention. Furthermore, since the microprocessors are reconfigurable (no code change), the protocol allows for dynamic connections, disconnections and reconnections. Therefore this project is contains both the explanation , rationale and description of this dynamically reconfigurable protocol, as well as the instant message application program used to demonstrate the protocol.
High level design
The high level design for our project consists of 3 microprocessors and associated boards, as well as an 8-bit LED series (which is used to in place of an LCD screen to keep costs down), a button set (keypad), and a series of wire interconnects. There is also the development of a protocol designed to allow the individual microprocessors to send messages to each other. Unlike a typical communications protocol, there is no multi-way bus, but rather each wire acts as solely an input and an output. Furthermore, each microprocessor connects to only two other microprocessors. This thereby forms a “line” like structure out of the set of microprocessors. While our setup (and budget) only allows for 3 microprocessors, our protocol as it currently stands can be used with up to 7, and in theory it could be expanded to allow for a longer chain of microprocessors. Using our mulit-microprocessor setup, we built an instant messaging application on top of the protocol and the microprocessors setup. While our application may not be that innovative or productive, it is more of a proof of concept for that which can be done with these microprocessors, in that we’re trying to make a protocol that allows for easy reconfiguration, as well as robustness and lightweight-ness.
We felt that our own protocol would not only be fun and exciting to develop, but would remove us from any intellectual property issues. Additionally, since we weren’t using a standard protocol, there were (and still aren’t) any standards that apply. Furthermore, since our protocol is developed for use over regular short distant wires, there is no government regulation that is applicable. With regards to instant messaging however, it is more of an application of what our protocol can do. While there are ethical issues with that, such as storing transcripts of the conversation as well as perhaps a security breech, we do not consider these. Our protocol is certainly not “snooping proof” and is not a secure protocol. That being said, security could be added, for example an encryption scheme could be used to encrypt the data, thereby providing a secure message passing medium.
As for the hardware and the software, we could obviously have used a hardware based protocol, for example most Ethernet based communications is done in hardware because it is so much faster to do it on-board. That being said, we were developing on a very slim budget, and did not have the capability to fabricate our own custom chip, as well as wish to. Our protocol is dynamic precisely because it is written in software, and allows the software to make higher level decisions based on a better all around knowledge of the situation (as there is more RAM, so software will have a better picture of the overall state of the machine and the scenario).
At first we really wanted to make our protocol an additional component of the operating system (that was translated to the Mega32 microprocessor by Bruce Land, and is available on the ECE 476 website). Just like this operating system contains components for shared resources (eg: semaphores/locks) and has constructs for message passing between threads on a single microprocessor we wanted to add the ability for threads on different MCUs to communicate with each other. Sadly this was not to be, as we could not get the operating system working with the latest version of the compiler that our class had licensed, and so we had to ditch the idea of adding (or extending) the operation system, and instead chose to take a less separate approach, as that is simply the only way to accomplish this without the operating system.
The Protocol
Any protocol is “a set of syntactic and semantic rules for exchanging information that includes (a) syntax of the information; (b) semantics of the information; and (c) rules for the exchange of information.”[1] Our protocol defines the timing and the specific electrical control signals necessary to transmit data (specifically a byte) between two microprocessors. Between each set of microprocessors there is a set of eight control lines, four being inputs to each processor and 4 being outputs for each processor. Since outputs of one processor act as inputs for the other processor, there are a total of eight control signals per processor connection. Remember that each processor can be connected to up to two other processors, so that a total of 16 control signals could be connected to each microprocessor.
Our protocol is interrupt driven, is clock independent, and handshakes each transaction. Additionally the protocol has a signal that is always high, that symbolizes whether the other processor is connected. Since we want our microprocessors to be dynamically reconfigurable, it was important to have clock independent. Furthermore, since we initially intended it to be an addition to the operating system, it was important (in that it not take too many system – ie: OS - resources) to be interrupt driven, instead of polling from its own thread. It turns out that threads in the operating system really aren’t very lightweight (as opposed to a PC where threads are commonly referred to as lightweight processes because the overhead associated with processes, as well as the memory requirements, are basically non-existent. However, on the Mega32 we had to really take into account memory constraints, which really only allow for 5 individual threads. Furthermore, the stack space for the threads is basically relegated to being statically allocated, so you can’t even have processes that “disappear”. This also caused us problems when we wanted to have dynamically sized data structures, but we settled on fixed size structures instead, and created a “rotating list” (discussed further below).
Each microprocessor has 16 control signals, eight are for one connection and eight are for the other. Each set of eight is made exactly to correspond (in order) with the previous set. Said another way, you can divide the set of 16 control signals into sets (two of them) of eight control signals, eight go to the processor on the right, and eight go to the processor on the left. But the processor on the left, is connected to this processor and this processor is on its right, so in essence the set of eight control signals for the processor on the left, directly corresponds inversely to the eight control signals for the processor on the right. Then, since this is a two way connection, each set of eight control signals is further divided up into two sets of four control signals, one goes in one direction and the other goes in the other direction. There is a similar division here in that each set of four is made exactly to correspond (in order) with the previous set (similar to the case of the set of eight). Below is a table of ports, and where each port plugs into and each control signal’s purpose:
Control Signal Name |
Purpose/Description |
Destination (where it plugs
into) |
Port |
|
Bus In (From) Right |
A single bit bus where the actual bits are received (from the processor on the right). |
Bus Out (To) Left |
|
|
Is Connected (In-From) Right |
Detects whether there is a processor connection to the right. |
Is Connected (Out-To) Left |
|
|
Done In (From) Right |
Detects whether the processor on the right has received the sent bit. |
Done Out (To) Left |
|
|
Ready In (From) Right |
Detects when the processor on the right wants to sent a bit. This raises the “receive-right” interrupt and begins a bit transmission. |
Ready Out (To) Left |
|
|
Ready Out (To) Right |
Set when this processor wants to initiate a bit transfer to the processor on its right. |
Ready In (From) Left |
|
|
Done Out (To) Right |
Set when this processor wants to acknowledge that it has received a bit from the processor on the right. |
Done In (From) Left |
|
|
Bus Out (To) Right |
A single bit bus where the actual bits are sent (to the processor on the right). |
Bus In (From) Left |
|
|
Is Connected (Out-To) Right |
Always high. Tells the processor on the right that there is a processor on its left. |
Is Connected (In-From) Left |
|
|
Bus In (From) Left |
A single bit bus where the actual bits are received (from the processor on the left). |
Bus Out (To) Right |
|
|
Is Connected (In-From) Left |
Detects whether there is a processor connection to the right. |
Is Connected (Out-To) Right |
|
|
Done In (From) Left |
Detects whether the processor on the right has received the sent bit. |
Done Out (To) Right |
|
|
Ready In (From) Left |
Detects when the processor on the right wants to sent a bit. This raises the “receive-right” interrupt and begins a bit transmission. |
Ready Out (To) Right |
|
|
Ready Out (To) Left |
Set when this processor wants to initiate a bit transfer to the processor on its right. |
Ready In (From) Right |
|
|
Done Out (To) Left |
Set when this processor wants to acknowledge that it has received a bit from the processor on the right. |
Done In (From) Right |
|
|
Bus Out (To) Left |
A single bit bus where the actual bits are sent (to the processor on the right). |
Bus In (From) Right |
|
|
Is Connected (Out-To) Left |
Always high. Tells the processor on the right that there is a processor on its left. |
Is Connected (In-From) Right |
|
The procedure to actually send a byte works as follows. The processor that wants to sent the byte first needs to decide which adjacent processor to send to. As this is an example, we will assume that the processor that we are considering (processor1) is sending a byte to the processor on its right (processor2). To initiate a transfer, and to ensure proper timing, processor1 places the first bit of the byte on the Bus Out (To) Right. It then raises the Ready Out (To) Right line. Processor2 handles the interrupt generated as it’s Ready In (From) Left line goes high, reads the bit and places it in the appropriate spot count in the byte. It then sets it’s Done Out (To) Left line high. All this while Processor1 has been busy waiting for it’s Done In (From) Right line to go high. When it does go high, it sets it’s Ready Out (To) Right to low. Just as processor1 was busy waiting for it’s Done In (From) Right line to go high, so to processor 2 is busy waiting for its Ready In (From) Left line to go low. When it goes low, the hand shake is completed from both sides, and a single bit has been sent. The reason for this very complex handshake is to ensure fail-fast behavior, as well as dynamic reconfiguration of the processors. Fail fast behavior means that if somehow the processors separate, and become un-connected, then the both receives and sends will reset themselves, and not block. A similar process occurs for sending to the left (from the right). Additionally, since the protocol is interrupt driven, the processor can receive two simultaneous transmissions. However, sending is synchronous, and therefore bytes can only be sent in one direction at a time per processor.
The Protocol – Part 2
While the above protocol specified simple byte transfers in a single direction, and only to adjacent neighbors. We also constructed a multiprocessor communications protocol layer that is built on top of the lower level, byte transfer protocol. The first order of business that this layer performs is an initial numbering of the processors. This basically allows each processor to have an “id” (similar to an IP address) associated with it. Because the processors are laid out in a line, there will always be a “left-most” processor (granted that one could create a ring-based protocol, but we found that a line would be more interesting in terms of instant messaging). This “left most” processor is given an address of 1. When processors are connected to the right, they get an address that is one greater than the processor that they connected to. If a processor is attached on the left, it sends a propagating control packet down the line that re-initializes all of the addresses. Also, if a processor is disconnected, it may either form a new chain, and the processors that were disconnected can detect this and initialize their own chains (depending on a left most processor etc). The same process if followed. Our design allows for 7 processors in a line, though another protocol could allow for more.
Packets
Packets include an 8 bit header, with 3 bits dedicated to the processor address that send the packet, 3 bits dedicated to the processor address of the processor that is to receive the packet. The remaining two bits of the header, indicate the type of packet. Currently there are only two kinds of packets, data packets and the control packet that clears the address and replaces it with the “from-address” plus 1. Because the processors are laid out in a line with addresses in incrementing order, if a processor receives a packet with a destination address other than its own, it can forward it either to the left or to the right depending on if the destination address is greater (it should forward the packet to the right) than its own address, or if it is less than its own address (it should forward it to the left). Issues that could potentially come up are if a processor is newly connected to the set (or some processors are disconnected), if a packet is in the middle of going down the processor line. In this case, the packet may pass the proper processor, or might even be lost. This protocol layer is not-reliable (and is in fact fail-fast) so there are no acknowledgements build into the system, though because of the base protocol, it would be possible to add reliable sending. We chose not to, because reconfiguration while running a program is not recommended, as it is very hard to get all of the pins to touch at exactly the same moment, without any interference, or voltage fluctuations. While according to the protocol specifications, this is permitted, and in fact the code allows for this, the specific hardware may or may not support this.
In addition to the packet header, each packet transmits 2 bytes of data (16-bits). On a very small architecture, that is not very robust, we feel that this is a good tradeoff to those applications that only wish to send small packets, and those that wish to send large packets. Remember that packet transmission is synchronous (even when propagating down the processor chain) so that it would be possible to build an additional layer that sent multiple packets.
Project Design
As explained above, there are many components of this project. First off, there is the hardware component, of wiring all of the port pins to the MCU in the correct order, as well as powering the setup, connecting the keypad and LEDs in a user friendly way and making all of the interconnections just work. Most of the wires are “detachable” and reconfigurable on the fly, thereby keeping with our theme of dynamic connections that are reconfigurable at runtime. Since we have explained the interconnections pretty well in the port description above, we believe that someone else could use our protocol. As for the demo instant messaging program, well, the LEDs are outputs on port C and the keypad is an input on port B. Otherwise, it’s just as simple as making it look nice and setting up STK boards, or similar protoboards.
Much of the protocol has been explained able, and while there is a lot of code that implements the protocol, most of it is self explanatory. One of the key underlying software components though that was not discussed as a list, or queue, that keeps an in-order representation of the packets, or bytes, that have been received, to be read later. This was necessary, originally, because we were going to use an operating system, but it is still necessary in our design in that receiving data still asynchronous and from interrupts. Additionally, since we wanted our code modular, and more easily ported over to the operating system, we chose to stick with our queues.
What is so special about these queues you might ask? Well, it turns out that dynamic memory allocation on the Mega32s is really annoying. Therefore, in the operating system, and in all of our labs we have done static memory allocation. It is also faster though if you’re not using it, then it’s a waste. I was actually sort of surprised to find that stacks for the OS threads were statically allocated instead of dynamically allocated. Perhaps this is to that memory allocation calls were never used, as they would require disabling interrupts, of protecting with locks/semaphores. Basing our design off of the operating system, we chose to make a queue using static memory allocation. Your queue can reach a maximum of slots, determined in a define construct. Element addition is O(1) and so is element removal. Additionally, there is no extra storage necessary for the queue other than the actual data (ie: no pointers to free blocks, like the OS etc.) This is because we keep the index of the first element and the index of the last element in variables. Additionally, our list “cycles” so that if you add two elements, and then remove the first element, then your single element is left at position 2 (zero based index 1) of the list. In this way, you can have your queue “wrap” around the list. It’s a pretty fast implementation, though if too many elements build up in the list, than elements will get overwritten, so it is necessary to make the queue large enough.
As we have referenced before, we very much wanted this protocol to be an extension of the operating system, but we could not get it working. We were in fact very disappointed. As for code, we wrote all of the code ourselves, and came up with all of the coding constructs ourselves. There is NO borrowed code (except perhaps for a very basic program shell from project 0 on the ECE 476 webpage), nor is there any code that is licensed in any way, even open source. Additionally the protocol design is ours alone, we did look at other not-similar protocol designs, like SPI, but chose the interrupt driven protocol for better use with the operating system, and better performance (as we didn’t need a thread to be bothered with it.)
Results and conclusions
So in the end, our software does everything that we intended, but sadly, we were not able to demo using a line of three microprocessors as the lab ran out of the components necessary for our design. We still have 2 microprocessors that communicate perfectly and use the address scheme. However, no forwarding/routing is involved in this case, so while still very interesting, it’s not the best that we could do. We still feel as though our system supports such and we did implement at least one of each necessary and were able to show a proof of concept instant messaging system which works with our two processors and uses our full protocol. That being said, our system runs very efficiently and effectively. We can detect no lag, and everything seems to be in working order. It’s very exciting to see something you build become a reality, and we’re very proud.
Our design and project doesn’t interfere with anything that we could tell.
Ethics
We believe that our design is ethical. We have already discussed the ethics with respect to instant messaging. I have copied it again here for posterity. While there are ethical issues with instant messaging, such as storing transcripts of the conversation as well as perhaps a security breech, we do not consider these. Our protocol is certainly not “snooping proof” and is not a secure protocol. That being said, security could be added, for example an encryption scheme could be used to encrypt the data, thereby providing a secure message passing medium. In terms of ethics on our part, we feel that we have lived up to our ethical responsibility and in fact furthered science in this area in that we created something new and on our own. We believe this new technology to be useful, not only for us, but for others. Furthermore, our project is not harmful to people or other creatures or things, and certainly treats everybody fairly. We believe that we have accurately represented what our protocol can do, and even give a reference implementation of it. We are even going so far as to permit use of our code under a Creative Commons license, thereby allowing others to utilize and improve our code, and to hopefully help out others.
Appendices:
Cost List
|
Part Name |
Cost ($) |
|
2 Mega32s with boards: |
13x2 = 26 |
|
1 Power Supply (Wall Wart) |
5 |
|
1 Keypad |
6 |
|
1 Small Board |
1 |
|
Total: |
$38 |
Task Division
We feel that we worked very well together and really did all of the tasks together. That being said, because of our differing interests, Jimmy worked more on the hardware end, and Etan worked more on the software end.
Code
Our code can be downloaded from: http://www.ebukiet.net/476/Code.zip.
License
This software is licensed under the CC-GNU GPL.
References
· ECE 476 Website: http://instruct1.cit.cornell.edu/courses/ee476/