Methods for maximizing routability in a programmable interconnect matrix having less than full connectability

A method for designing a programmable interconnect matrix, comprising the steps of:

• providing a plurality n.sub.in of input conductors;
• providing a plurality n.sub.out of output conductors wherein n.sub.in is greater than n.sub.out ;
• providing a plurality n.sub.mux of multiplexors, each multiplexor having w.sub.mux inputs for coupling to input conductors and one output being coupled to one of the n.sub.out output conductors, wherein w.sub.mux is less than n.sub.in ;
• and
• connecting each of a subset m of the n.sub.in input conductors to x of the n.sub.mux multiplexors, wherein x is equal to r rounded up to a nearest integer, r is not an integer and is equal ##EQU16## and m is equal to ((n.sub.in)(x)-(n.sub.out)(w.sub.mux));
• connecting each of (n.sub.in -m) input conductors to y of the n.sub.mux multiplexors, wherein y is equal to r rounded down to a nearest integer, the n.sub.in input conductors being coupled to the n.sub.mux multiplexors such that each multiplexor shares q input conductors with at least two other multiplexors, wherein q is equal to ##EQU17## and wherein each of the n.sub.mux multiplexors shares at most q input signals with every other multiplexor.

A method for designing a programmable interconnect matrix, comprising the steps of:

• providing a plurality n.sub.in of input conductors;
• providing a plurality n.sub.out of output conductors wherein n.sub.in is greater than n.sub.out ;
• providing a plurality n.sub.mux of multiplexors, each multiplexor having w.sub.mux inputs for coupling to input conductors and one output being coupled to one of the n.sub.out output conductors, wherein w.sub.mux is less than n.sub.in ;
• and
• connecting each input conductor to r multiplexors such that each multiplexor of a subset s of the n.sub.mux multiplexors shares v input conductors with at least one other multiplexor and each of (n.sub.mux -s) multiplexors share u input conductors with at least one other multiplexor, wherein r is equal to ##EQU18## u is equal to q rounded down to a nearest integer, v is equal to q rounded up to a nearest integer, q is not an integer and is equal to ##EQU19## and s is equal to ((n.sub.mux)(v)-((n.sub.mux)(w.sub.mux)-n.sub.in)), and wherein each of the n.sub.mux multiplexors shares at most v input signals with every other multiplexor.

A method for designing a programmable interconnect matrix, comprising the steps of:

• providing a plurality n.sub.in of input conductors;
• providing a plurality n.sub.out of output conductors wherein n.sub.in is greater than n.sub.out ;
• providing a plurality n.sub.mux of multiplexors, each multiplexor having w.sub.mux inputs for coupling to input conductors and one output being coupled to one of the n.sub.out output conductors, wherein w.sub.mux is less than n.sub.in ;
• and
• connecting each of a subset m of the n.sub.in input conductors to x of the n.sub.mux multiplexors, wherein x is equal to r rounded up to a nearest integer, r is not an integer and is equal ##EQU20## and m is equal to ((n.sub.in)(x)-(n.sub.out)(w.sub.mux));
• connecting each of (n.sub.in -m) input conductors to y of the n.sub.mux multiplexors, wherein y is equal to r rounded down to a nearest integer, the n.sub.in input conductors being coupled to the n.sub.mux multiplexors such that each multiplexor of a subset s of the n.sub.mux multiplexors shares v input conductors with at least one other multiplexor and each of (n.sub.mux -s) multiplexors share u input conductors with at least one other multiplexor, wherein u is equal to q rounded down to a nearest integer, v is equal to q rounded up to a nearest integer, q is not an integer and is equal to ##EQU21## and s is equal to ((n.sub.mux)(v)-(n.sub.mux)(w.sub.mux)-n.sub.in)), and wherein each of the n.sub.mux multiplexors shares at most v input signals with every other multiplexor.

A programmable interconnect matrix designed using a method comprising the steps of:

• providing a plurality n.sub.in of input conductors;
• providing a plurality n.sub.out of output conductors wherein n.sub.in is greater than n.sub.out ;
• providing a plurality n.sub.mux of multiplexors, each multiplexor having w.sub.mux inputs for coupling to input conductors and one output being coupled to one of the n.sub.out output conductors, wherein w.sub.mux is less than n.sub.in ;
• and
• connecting each input conductor to r multiplexors such that each multiplexor shares q input conductors with at least two other multiplexors, wherein r is equal to ##EQU22## and q is equal to ##EQU23## and wherein each of the n.sub.mux multiplexors shares at most q input signals with every other multiplexor.

A programmable interconnect matrix designed using a method comprising the steps of:

• providing a plurality n.sub.in of input conductors;
• providing a plurality n.sub.out of output conductors wherein n.sub.in is greater than n.sub.out ;
• providing a plurality n.sub.mux of multiplexors, each multiplexor having w.sub.mux inputs for coupling to input conductors and one output being coupled to one of the n.sub.out output conductors, wherein w.sub.mux is less than n.sub.in ;
• and
• connecting each of a subset m of the n.sub.in input conductors to x of the n.sub.mux multiplexors, wherein x is equal to r rounded up to a nearest integer, r is not an integer and is equal ##EQU24## and m is equal to ((n.sub.in)(x)-(n.sub.out)(w.sub.mux));
• connecting each of (n.sub.in -m) input conductors to y of the n.sub.mux multiplexors, wherein y is equal to r rounded down to a nearest integer, the n.sub.in input conductors being coupled to the n.sub.mux multiplexors such that each multiplexor shares q input conductors with at least two other multiplexors, wherein q is equal to ##EQU25## and wherein each of the n.sub.mux multiplexors shares at most q input signals with every other multiplexor.

A programmable interconnect matrix designed using a method comprising the steps of:

• providing a plurality n.sub.in of input conductors;
• providing a plurality n.sub.out of output conductors wherein n.sub.in is greater than n.sub.out ;
• providing a plurality n.sub.mux of multiplexors, each multiplexor having w.sub.mux inputs for coupling to input conductors and one output being coupled to one of the n.sub.out output conductors, wherein w.sub.mux is less than n.sub.in ;
• and
• connecting each input conductor to r multiplexors such that each multiplexor of a subset s of the n.sub.mux multiplexors shares v input conductors with at least one other multiplexor and each of (n.sub.mux -s) multiplexors shares u input conductors with at least one other multiplexor, wherein r is equal to ##EQU26## u is equal to q rounded down to a nearest integer, v is equal to q rounded up to a nearest integer, q is not an integer and is equal to ##EQU27## s is equal to ((n.sub.mux)(v)-((n.sub.mux)(w.sub.mux)-n.sub.in)), and wherein each of the n.sub.mux multiplexors shares at most v input signals with every other multiplexor.

A programmable interconnect matrix designed using a method comprising the steps of:

• providing a plurality n.sub.in of input conductors;
• providing a plurality n.sub.out of output conductors wherein n.sub.in is greater than n.sub.out ;
• providing a plurality n.sub.mux of multiplexors, each multiplexor having w.sub.mux inputs for coupling to input conductors and one output being coupled to one of the n.sub.out output conductors, wherein w.sub.mux is less than n.sub.in ;
• and
• connecting each of a subset m of the n.sub.in input conductors to x of the n.sub.mux multiplexors, wherein x is equal to r rounded up to a nearest integer, r is not an integer and is equal ##EQU28## and m is equal to ((n.sub.in)(x)-(n.sub.out)(w.sub.mux));
• connecting each of (n.sub.in -m) input conductors to y of the n.sub.mux multiplexors, wherein y is equal to r rounded down to a nearest integer, the n.sub.in input conductors being coupled to the n.sub.mux multiplexors such that each multiplexor of a subset s of the n.sub.mux multiplexors shares v input conductors with at least one other multiplexor and each of (N.sub.mux -s) multiplexors shares u input conductors with at least one other multiplexor, wherein u is equal to q rounded down to a nearest integer, v is equal to q rounded up to a nearest integer, q is not an integer and is equal to ##EQU29## and s is equal to ((n.sub.mux)(v)-((n.sub.mux)(w.sub.mux)-n.sub.in)), and wherein each of the n.sub.mux multiplexors shares at most v input signals with every other multiplexor.

A programmable interconnect matrix comprising:

• a plurality n.sub.in of input conductors;
• a plurality n.sub.out of output conductors, wherein n.sub.out is less than n.sub.in ;
• and
• a plurality n.sub.mux of multiplexors, wherein n.sub.mux is greater than n.sub.out, each multiplexor having an output coupled to one of the n.sub.out output conductors and a plurality w.sub.mux of inputs each coupled to an input conductor, wherein w.sub.mux is less than n.sub.in and a maximum of n.sub.out multiplexors are selected to couple n.sub.in input conductors to the n.sub.out output conductors.

A method for designing a programmable interconnect matrix, comprising the steps of:

• providing a plurality n.sub.in of input conductors;
• providing a plurality n.sub.out of output conductor wherein n.sub.in is greater than n.sub.out ;
• providing a plurality n.sub.mux of multiplexors, each multiplexors having w.sub.mux inputs for coupling to input conductors and one output being coupled to one of the n.sub.out output conductors, wherein w.sub.mux is equal to (n.sub.in -n.sub.mux +1);
• connecting each input conductor to a plurality of multiplexors such that each multiplexor shares q input conductors with at least two other multiplexors and each multiplexor shares at most q input signal as with every other multiplexor, wherein q is equal to ##EQU30##